CANDY - Chia kẹo 1
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, Python, Ruby, Rust, Scratch, Swift
An và Bình là hai anh em. Ba của An sau chuyến đi công tác xa nhà trở về, mua cho An và Bình ~N~ gói kẹo, gói thứ ~i~ có ~A_i~ viên kẹo.
Để tránh việc tranh giành kẹo lẫn nhau, ba của An đã thống nhất việc chia kẹo theo cách sau:
- Trước hết, ba của An chọn ra một số nguyên ~k~ (với ~1 ≤ k ≤ N~).
- An sẽ được chia các gói kẹo từ ~1~ đến ~k~. Phần còn lại (các gói kẹo từ ~k + 1~ đến ~N~) sẽ được chia cho Bình.
Để tránh sự phân bua giữa hai anh em, ba của An muốn lựa chọn chỉ số ~k~ sao cho chênh lệch giữa tổng số lượng viên kẹo của hai anh em là nhỏ nhất có thể. Hãy giúp ông thực hiện điều này.
Input
- Dòng đầu tiên gồm số nguyên ~N~ ~(2 ≤ N ≤ 200000)~ - số gói kẹo;
- Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~ ~(1 ≤ A_i ≤ 10^9)~ - số viên kẹo trong từng gói kẹo.
Giới hạn:
- Subtask#1 ~(50\%\text{ số điểm}): N ≤ 2000~;
- Subtask#2 ~(50\%\text{ số điểm}):~ Không có ràng buộc gì thêm.
Output
In ra chênh lệch lượng kẹo nhỏ nhất có thể.
Sample
Input #1
5
5 1 3 2 6
Output #1
1
Input #2
6
4 5 3 6 1 2
Output #2
3
Input #3
2
100 100
Output #3
0
Hint
- Trong ví dụ thứ nhất, nếu chọn ~k = 3~ thì tổng số kẹo An được chia là ~5 + 1 + 3 = 9~, tổng số kẹo Bình được chia là ~2 + 6 = 8~, chênh lệch lượng kẹo là ~|9 − 8| = 1~.
- Trong ví dụ thứ hai, có hai cách chọn k tối ưu:
- Chọn ~k = 2~. Tổng số kẹo An được chia là ~4 + 5 = 9~, tổng số kẹo Bình được chia là ~3 + 6 + 1 + 2 = 12~, chênh lệch lượng kẹo là ~|9 − 12| = 3~.
- Chọn ~k = 3~. Tổng số kẹo An được chia là ~4 + 5 + 3 = 12~, tổng số kẹo Bình được chia là ~6 + 1 + 2 = 9~, chênh lệch lượng kẹo là ~|12 − 9| = 3~.
Problem source: Kc97ble - Free Contest
Bình luận
include <bits/stdc++.h>
using namespace std;
bool snt(long long x) { if(x<2) return false; for(int i=2;i<=sqrt(x);i++) { if(x%i==0) return false; } return true; } bool bruh(long long n) { for(int i=1; i<=n; i++){ if(snt(i)==true){ if(n%i==0 and snt(n/i)==true){ return true; } } } return false; }
int main() { int t; cin>>t; while(t--){ int n; cin>>n; if(bruh(n)==true){ cout<<"YES"<<endl; } else cout<<"NO"<<endl; } return 0; }
include <iostream>
bool isPrime(int num) { if (num < 2) { return false; } for (int i = 2; i * i <= num; ++i) { if (num % i == 0) { return false; } } return true; }
int main() { int t; std::cin >> t;
}
.