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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844

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 *