Question

[Lê Thanh Hà]

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

Answer 1

[Mạc Thị Như Quỳnh]

Ở đâ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).