COUNT - Chia bánh
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Toudou có ~N~ cái bánh, mỗi cái bánh mang năng lượng ~W_i~. Có bao nhiêu cách chia đống bánh ra thành ~3~ phần liên tiếp sao cho mỗi chiếc bánh thuộc đúng một phần và tổng giá trị năng lượng của 3 phần là bằng nhau?
Nói cách khác, hãy đếm số cặp ~(i, j)~ sao cho ~2 ≤ i ≤ j ≤ n−1~ và:
$$\sum_{k=1}^{i-1}a_k=\sum_{k=i}^{j}a_k=\sum_{k=j+1}^{N}a_k$$
Input
- Dòng đầu tiên, gồm một số nguyên ~N~;
- Dòng tiếp theo, gồm ~N~ số nguyên ~W_i~ - là giá trị năng lượng của mỗi cái bánh.
Giới hạn:
- ~1 ≤ N ≤ 500000; |W_i| ≤ 10^9~. Trong đó ~30\%~ số test có ~1 ≤ N ≤ 5000~.
Output
- Gồm một dòng duy nhất là kết quả bài toán.
Sample
Input #1
5
1 2 3 0 3
Output #1
2
Input #2
4
0 1 -1 0
Output #2
1
Problem source: Kc97ble - Free Contest
Bình luận
Bài này cũng không cần đến thủ thuật nhiều j lắm , ae cứ nghĩ đơn giản : -Do chia làm 3 phần bằng nhau nên tổng phải chia hết cho 3 trước đã , nếu không in ra 0 -Chọn mốc = s[n]/3 , đặt 2 biến count =0 và result =0 (result sẽ là kết quả in ra) -Ta chọn thằng temp =0 sẽ cộng dần dần mảng a từ a[0] -Cộng đến lúc mà temp=mốc thì ta cho count ++ , count này chính là cách chọn thằng i (bởi vì đằng sau thằng a[i] có thể là giá trị 0 nên ta sẽ có thêm cách chọn i mới ) , duyêtj tiếp đến khi nào temp=mốc2 , thì cho temp +=count , khi i chay den n-1 se ket thuc va duoc ket qua cuoi cung la count ví dụ {1,1,1,0,0,2,1,0,3} thì khi temp =3 (đầu tiên a[i]=1(i=2)) thì count =1 , khi chạy tiếp thì a[3]=0 =>count =2,tiếp nữa a[4]=0=>count =3 ... đến a[6], temp=6 thì result =count , a[7]=>temp vẫn bằng 6 thì temp =count +count , nó như kiểu ae lấy tổ hợp thỏa mãn ấy ... Vậy cuối cùng temp =2count.