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 ≤ ...
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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | 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. |
