Hướng dẫn giải của Tổng bằng K (đề HSG 12 Phú Thọ 2023-2024)
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
Cho dãy 1, 2, ..., N và số K. Đếm số cặp (a, b) trong dãy sao cho a + b = K, trong đó (a, b) và (b, a) tính là một cặp (theo ví dụ, cặp có a = b không được tính). Đọc từ CAU1.INP, ghi ra CAU1.OUT.
Sub 1: Vét cạn — ~O(K)~
Thử mọi a sao cho 2a < K, với b = K - a. Nếu b ≤ N thì đếm thêm một cặp. Cách này đúng với K nhỏ nhưng K có thể lên tới 10^18.
Kết quả chấm: đạt 22/24 test (SUB ok 22/24, TLE 2, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
}
long long n, k;
cin >> n >> k;
// Vét cạn: thử mọi a sao cho a < b = k - a (đếm cặp không trùng nhau), b <= n
long long dem = 0;
for (long long a = 1; 2 * a < k; a++) {
long long b = k - a;
if (b <= n) dem++;
}
cout << dem << "\n";
return 0;
}
Sub 2: Đếm bằng công thức — ~O(1)~
Cặp (a, b) với a < b, a + b = K, 1 ≤ a, b ≤ N. Điều kiện b ≤ N tương đương a ≥ K - N, và a < b tương đương a ≤ (K-1)/2. Kết hợp với a ≥ 1, số cặp là hi - lo + 1 với lo = max(1, K - N), hi = (K-1)/2, và bằng 0 nếu hi < lo. Dùng long long vì K đến 10^18.
Kết quả chấm: đạt 24/24 test
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
}
long long n, k; // N và K có thể lên tới 10^18
cin >> n >> k;
// Cặp (a, b) với a < b, a + b = K, 1 <= a, b <= N:
// a phải thỏa a >= max(1, K - N) (để b <= N) và a <= (K - 1) / 2 (để a < b)
long long lo = max(1LL, k - n);
long long hi = (k - 1) / 2;
long long dem = (hi >= lo) ? hi - lo + 1 : 0;
cout << dem << "\n";
return 0;
}
Bình luận