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
``` cpp
include<bits/stdc++.h>
define el '\n'
define ll long long
define N 1000000
using namespace std; ll n,w[N+3],pre[N+3]; int main(){ iosbase::syncwith_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>n; for(ll i=1;i<=n;i++) cin>>w[i]; for(ll i=1;i<=n;i++) pre[i]=pre[i-1]+w[i]; if(pre[n]%3!=0) {cout << 0 << el;return 0;} ll k=pre[n]/3; ll ans=0,res=0,cur=0; for(ll i=1;i<=n;i++){ ans+=w[i]; if(ans==k) res++; if(ans==2*k) cur+=res; } cout << cur << el; return 0; }
include <bits/stdc++.h>
using namespace std; long long n, t=0, a[1000009]; int main() { iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++)
{ t += a[i]; } if (t % 3 != 0) { cout << 0 << '\n'; return 0; } long long p = t / 3, d = 0, s = 0, ans = 0; for (int i = 1; i < n; i++) { ans += a[i]; if (ans == 2 * p) s += d; if (ans == p) d++; } cout << s << endl; return 0; }
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.