Bài 1. Tách dãy 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: - Dòng đầu ghi số N (N<=10^6) - Dòng tiếp theo ghi N số nguyên, các số cách nhau bởi dấu cách (Ai<=10^9) Output: - 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 Ví dụ: INPUT OUTPUT 5 1 3 4 0 4 1 2 3 2 3 4 -1

Thuật toán

Ở đâ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 $a_i$ là số thứ $i$ trong mảng đã cho. Lưu ý rằng số thứ $i$ trong mảng đã cho ($a_i$) được đánh số $i-1$ theo đề bài.

Ta định nghĩa một hàm $f(x)$ (mảng cộng dồn) theo công thức truy hồi như sau:

$f(x) = \left \{ {{0 \text{ nếu }x=0} \atop {f(x-1) + a_x \text{ nếu x > 0}}} \right.$

Ta có thể dễ dàng tính được giá trị của $f(i)$ với mọi $0 \leq i \leq n$ trong một vòng for.

Gọi $S$ là tổng các phần tử trong một phần của $A$ sau khi tách $A$ thành 3 phần như đề bài đã nói. Dễ thấy, $S$ bằng $\dfrac{1}{3}$ tổng dãy $A$. Mà theo định nghĩa hàm $f(x)$ như trên, ta có $S = \dfrac{1}{3} \times f(n)$. Do đó, ta có thể dễ dàng tính được $S$.

Việc bây giờ ta cần làm là tìm hai điểm cắt $i, j$ ($1 \leq i < j < n$) sao cho:

$a_1 + a_2 + \ldots + a_i = a_{i+1} + \ldots + a_j = a_{j+1} + \ldots + a_n$

Theo định nghĩa hàm $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) = S$

Từ đó ta nhận thấy cần tìm hai điểm cắt $i,j$ sao cho $f(i) = S$ và $f(j) = 2 \times 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)$.

Code (C++)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;

int n,a[maxn],idx;
long long f[maxn],S;

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        f[i] = f[i-1] + a[i];
    }
    if(f[n] % 3 != 0){
        // Do tat ca a[i] luon nguyen 
        // nen S phai nguyen
        cout << "-1";
        return 0;
    }
    S = f[n] / 3;
    idx = -1;
    for(int i=1;i<n;i++){
        if(idx == -1){
            // Chua tim thay f[i] = S
            if(f[i] == S) idx = i;
        }else{
            // Da tim thay f[i] = S
            // Chua tim thay f[j] = 2S
            if(f[i] == 2*S) {
                // In ra dap an theo yeu cau
                cout << idx-1 << ' ' << i-1;
                return 0;
            }
        }
    }
    cout << -1;
}

Bonus

Liệu bạn có thể làm được bài này nếu đề bài yêu cầu tách dãy thành $k$ phần ($k$ nhập từ bàn phím) thay vì $3$ phần cố định?

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    int n,a[1000005],s=0;
    cin >>n ;
    for (int i=0;i<n;i++){
        cin >> a[i];
        s+=a[i];
    }
    if (s%3!=0){
        cout << -1;
        return 0;
    }
    else {
        s/=3;
        int res=0,dem=0;
        for (int i=0;i<n;i++){
            if (res<s){
                res+=a[i];
            }
            if (res==s){
                cout << i << " ";
                res=0;
                dem++;
            }
            if (res>s) {
                cout << -1;
                break;
            }
            if (dem==2) break;
        }
    }
    return 0;
}