P152PROE spoj PTIT – Đếm số cách

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P152PROE/

1. Đề bài P152PROE spoj PTIT

Cho 1 dãy số gồm n số nguyên a[1], a[2], …, a[n]. Đếm số cách chia dãy thành 3 phần bằng nhau, hay nói cách khác là đếm số cặp i, j thỏa mãn:

Input

Dòng đầu tiên chứa số n (1 ≤ n ≤ 5*10^5).

Dòng thứ 2 gồm n số nguyên a[1], a[2], …, a[n] (0 <= |a[i]| <= 10^9) là các phần tử của dãy.

Output

In ra kết quả của bài toán.

Example

Test 1:

Input:

5

1 2 3 0 3

Output:

2

Test 2:

Input:

2

4 1

Output:

0

2. Gợi ý P152PROE spoj PTIT

Problem E: Đếm số cách

Gọi sum là tổng của tất cả các phần tử trong dãy:

Nếu sum % 3 != 0, trường hợp này bỏ qua, in ra 0.

Tại vị trí i mà tại đó tổng từ 1 đến i = sum/3, tính tổng số lượng các phần tử vị trí j (i < j <= n)

sao cho tổng từ j đến n = sum/3. Cộng dồn tổng vừa tìm được vào kết quả.

Để xử lý phần tìm số lượng vị trí j, ta có thể chuẩn bị trước 1 mảng bằng QHĐ (Mảng tổng).

3. code tham khảo P152PROE spoj PTIT

a. Code c++

#include <iostream>
using namespace std;

long long sum[500010];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int n1;
        cin >> n1;
        sum[i] = sum[i - 1] + n1;
    }
    long long tong = 0;
    if (sum[n] % 3 == 0)
    {
        int dem = 0;
        for (int i = n - 1; i>0; i--)
        {
            if (sum[i] == sum[n] / 3)
            {
                tong = tong + dem;
            }
            if (sum[i] == sum[n] / 3 * 2)
            {
                dem++;
            }
        }
    }
    cout << tong << endl;
}

b. Code pascal

const   fi='';
        nmax=5*100000;
type    data=longint;
var
        f:text;
        A,dem:array[0..nmax+1] of int64;
        n:data; res:int64;

procedure docfile;
var
        i,j:data;
        x:int64;
begin
        assign(f,fi); reset(f);
        readln(f,n);
        a[0]:=0;
        for i:=1 to n do
                begin
                        read(f,x);
                        a[i]:=a[i-1]+x;
                end;
        close(f);
end;

procedure xuli;
var     i,j:data;
        dem:int64;
begin
        res:=0; dem:=0;
        if a[n] mod 3 <>0 then exit;
        for i:=n-1 downto 1 do
                begin
                if a[n] div 3 = a[i] then
                        inc(res,dem);
                if (a[n] div 3)*2 = a[i] then
                        inc(dem)
                end;

end;

begin
        docfile;
        xuli;
        writeln(res);
end.