Hướng dẫn giải của [Beginner Free Contest 03] MILITARY
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm số tổng khác nhau của dãy N số, trong đó các số nằm trong [A, B] và dãy phải có ít nhất một số A và một số B. Ví dụ N=4, A=4, B=6 cho 5 tổng khác nhau.
Sub 1: Vét cạn tập tổng — ~O(N · (B-A)·|tập tổng|)~
Bắt đầu với tập tổng {A + B} (hai số bắt buộc). Mỗi lần thêm một số bất kỳ trong [A, B] thì tạo tập tổng mới bằng cách cộng từng giá trị. Sau khi thêm đủ N - 2 số, số phần tử của tập là đáp số. Đúng nhưng chỉ chạy được khi N và B - A nhỏ.
Kết quả chấm: 11/20 (SUB ok 11/20, TLE 9, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, A, B;
cin >> n >> A >> B;
// Vet can: tap cac tong co the tao ra tu cac so trong [A, B], trong do co du A va B
if (A > B) { cout << 0 << "\n"; return 0; }
if (n == 1) { cout << (A == B ? 1 : 0) << "\n"; return 0; }
set<long long> cur;
cur.insert(A + B); // hai so bat buoc la A va B
for (long long i = 3; i <= n; i++) {
set<long long> nxt;
for (long long s : cur)
for (long long v = A; v <= B; v++) nxt.insert(s + v); // them mot so bat ky trong [A, B]
cur = nxt;
}
cout << cur.size() << "\n";
return 0;
}
Sub 2: Các tổng tạo thành đoạn liên tiếp — ~O(1)~
Tổng nhỏ nhất là A + B + (N-2)·A, tổng lớn nhất là A + B + (N-2)·B. Mọi giá trị ở giữa đều đạt được vì mỗi số có thể tăng thêm 1 đơn vị trong [A, B]. Vậy đáp số là (N-2)(B-A) + 1. Trường hợp N = 1 hoặc A > B được xử lý riêng.
Kết quả chấm: 20/20 (PASS 20/20)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, A, B;
cin >> n >> A >> B;
// Day gom N so, trong do bat buoc co A va B, cac so con lai nam trong [A, B].
// Tong dat moi gia tri tu A + B + (N-2)*A den A + B + (N-2)*B, cac gia tri deu lien tiep.
if (A > B) { cout << 0 << "\n"; return 0; }
if (n == 1) { cout << (A == B ? 1 : 0) << "\n"; return 0; }
cout << (n - 2) * (B - A) + 1 << "\n";
return 0;
}
Bình luận