Hướng dẫn giải của Ủng hộ (đề HSG 9 Phú Thọ 2024-2025)
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
Lớp cần tìm số sách N có thể nhận, sao cho tổng sách của M và N (a + y) chia hết cho x và không vượt quá s, với y ≥ 1. Nếu có nhiều đáp án thì in theo thứ tự giảm dần, không có thì in -1.
Sub 1: Vét cạn — ~O(s)~
Thử mọi tổng t từ s xuống a+1, nếu t chia hết cho x thì số sách của N là t - a. Cách này đúng nhưng s có thể lên tới 10^9.
Kết quả chấm: đạt 16/20 test (SUB ok 16/20, TLE 4, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long s, x, a;
cin >> a >> x >> s;
// Vét cạn: thử mọi tổng t = a + y từ s xuống a+1 (y >= 1), lấy t chia hết cho x
bool co = false;
for (long long t = s; t >= a + 1; t--) {
if (t % x == 0) {
cout << t - a << " ";
co = true;
}
}
if (!co) cout << -1;
cout << "\n";
return 0;
}
Sub 2: Liệt kê các bội của x — ~O(s/x)~
Tổng t phải là bội của x nằm trong đoạn [a+1, s]. Bội lớn nhất không vượt quá s là (s/x)·x, bội nhỏ nhất ≥ a+1 là ⌈(a+1)/x⌉·x. Nếu bội lớn nhất nhỏ hơn bội nhỏ nhất thì in -1. Ngược lại đi từ bội lớn xuống bội nhỏ với bước x và in t - a. Số đáp án không quá 10^5 nên in được hết.
Kết quả chấm: đạt 20/20 test
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, x, s; // a: sách của M; x: ước; s: tổng sách nhận được
cin >> a >> x >> s;
// Tổng sách của M và N là t = a + y, phải chia hết cho x và t <= s, t >= a + 1 (y >= 1)
long long tmax = (s / x) * x; // bội của x lớn nhất không vượt quá s
long long tmin = ((a + 1 + x - 1) / x) * x; // bội của x nhỏ nhất >= a + 1
if (tmax < tmin) {
cout << -1 << "\n";
return 0;
}
// Liệt kê các bội từ lớn xuống nhỏ, số sách của N là t - a
for (long long t = tmax; t >= tmin; t -= x)
cout << t - a << " ";
cout << "\n";
return 0;
}
Bình luận