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++

b. Code pascal

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *