Bài 4. Tách dãy (SPLITARR.*) Python:
Cho dãy A gồm N phần tử được đánh số từ 0..N-1. Tìm cách tách A thành ba phần sao cho tổng các phần tử trong ba phần là bằng nhau? * Input: đọc vào từ file văn bản SPLITARR.INP gồm : - Dòng đầu ghi số N (1 ≤ N ≤ 106); - Dòng tiếp theo ghi N số nguyên A0, A2, …, An-1 (|Ai|≤109). Các số cách nhau bởi một dấu cách * Output: ghi ra file văn bản SPLITARR.OUT kết quả gồm hai chỉ số i, j thỏa mãn 0 ≤ i<j ≤ N sao cho i, j chia dãy thành 3 mảng con có tổng bằng nhau. Nếu không tồn tại cách chia, in ra -1 *example:
SPLITARR.INP | SPLITARR.OUT |
5 1 3 4 0 4 | 1 2 |
3 2 3 4 | -1 |
Ở đây mình chỉ chấp nhận một cách chia dãy thành 3 phần có tổng bằng nhau và khác rỗng.
Gọi aiai là số thứ ii trong mảng đã cho. Lưu ý rằng số thứ ii trong mảng đã cho (aiai) được đánh số i−1i−1 theo đề bài.
Ta định nghĩa một hàm f(x)f(x) (mảng cộng dồn) theo công thức truy hồi như sau:
f(x)={0 nếu x=0f(x−1)+ax nếu x > 0f(x)={0 nếu x=0f(x−1)+ax nếu x > 0
Ta có thể dễ dàng tính được giá trị của f(i)f(i) với mọi 0≤i≤n0≤i≤n trong một vòng for.
Gọi SS là tổng các phần tử trong một phần của AA sau khi tách AA thành 3 phần như đề bài đã nói. Dễ thấy, SS bằng 1313 tổng dãy AA. Mà theo định nghĩa hàm f(x)f(x) như trên, ta có S=13×f(n)S=13×f(n). Do đó, ta có thể dễ dàng tính được SS.
Việc bây giờ ta cần làm là tìm hai điểm cắt i,ji,j (1≤i<j<n1≤i<j<n) sao cho:
a1+a2+…+ai=ai+1+…+aj=aj+1+…+ana1+a2+…+ai=ai+1+…+aj=aj+1+…+an
Theo định nghĩa hàm f(x)f(x), ta có thể thấy ngay đẳng thức trên tương đương:
f(i)−f(0)=f(j)−f(i)=f(n)−f(j)=Sf(i)−f(0)=f(j)−f(i)=f(n)−f(j)=S
Từ đó ta nhận thấy cần tìm hai điểm cắt i,ji,j sao cho f(i)=Sf(i)=S và f(j)=2×Sf(j)=2×S
Công việc đến đây đã quá đơn giản do ta đã tính trước được tất cả các giá trị của f(x)f(x).