Hướng dẫn giải của Phần thưởng (đề Đồng Tháp 2021)
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
Gọi a là số kẹo của quán quân và b là số kẹo của á quân. Đề yêu cầu đếm số cặp (a, b) thỏa mãn a > b ≥ 1 và a + b ≤ n (không nhất thiết dùng hết kẹo). Ví dụ n = 5 có 4 cặp: (2,1), (3,1), (3,2), (4,1).
Sub 1: Vét cạn hai vòng lặp — ~O(n^2)~
Thử mọi cặp (a, b) với 1 ≤ b < a và kiểm tra a + b ≤ n rồi đếm. Đúng nhưng với n lớn thì quá chậm.
Kết quả chấm: đạt 21/30 test, 9 test quá thời gian, không sai test nào.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("PTHUONG.INP", "r")) {
freopen("PTHUONG.INP", "r", stdin);
freopen("PTHUONG.OUT", "w", stdout);
}
long long n;
cin >> n;
// Vét cạn: thử mọi cặp (a, b) với a > b >= 1 và a + b <= n
long long dem = 0;
for (long long a = 1; a <= n; a++)
for (long long b = 1; b < a; b++)
if (a + b <= n) dem++;
cout << dem << "\n";
return 0;
}
Sub 2: Với mỗi a, đếm số b hợp lệ — ~O(n)~
Với mỗi a cố định, b phải thỏa 1 ≤ b ≤ a - 1 và b ≤ n - a, nên số giá trị b là min(a - 1, n - a) (nếu dương). Cộng dồn theo a, chỉ còn một vòng lặp.
Kết quả chấm: đạt 28/30 test, 2 test quá thời gian, không sai test nào.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("PTHUONG.INP", "r")) {
freopen("PTHUONG.INP", "r", stdin);
freopen("PTHUONG.OUT", "w", stdout);
}
long long n;
cin >> n;
// Với mỗi a (số kẹo quán quân), b nằm trong [1, min(a-1, n-a)]
long long dem = 0;
for (long long a = 1; a <= n; a++) {
long long bmax = min(a - 1, n - a);
if (bmax > 0) dem += bmax;
}
cout << dem << "\n";
return 0;
}
Sub 3: Công thức — ~O(1)~
Đếm theo tổng s = a + b (s từ 3 đến n): với mỗi s có đúng floor((s-1)/2) cặp. Cộng lại ta được tổng bằng floor((n-1)^2 / 4).
Bẫy: với n đến 10^9, (n-1)^2 khoảng 10^18 nên phải dùng long long (vẫn nằm trong giới hạn của kiểu này).
Kiểm tra: n = 5 cho floor(4^2 / 4) = 4, đúng với ví dụ.
Kết quả chấm: đạt 30/30 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("PTHUONG.INP", "r")) {
freopen("PTHUONG.INP", "r", stdin);
freopen("PTHUONG.OUT", "w", stdout);
}
long long n;
cin >> n;
// Cặp (a, b) với a > b >= 1 và a + b <= n: đếm theo tổng s = a + b,
// tổng s ứng với floor((s-1)/2) cặp, cộng lại được floor((n-1)^2 / 4)
long long m = n - 1; // (n-1)^2 <= 10^18 nên không bị tràn long long
cout << m * m / 4 << "\n";
return 0;
}
Bình luận