Hướng dẫn giải của [200 đề thầy Đức] Bài 28: Tìm cách tiêu tiền
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
Cần tìm x, y \ge 0 sao cho xA + yB = N. Nếu có nhiều nghiệm thì in nghiệm có x nhỏ nhất (đúng với ví dụ 2 của đề).
Sub 1: Vét cạn hai vòng lặp — ~O(\frac{N}{A} \cdot \frac{N}{B})~
Duyệt x từ 0, rồi y từ 0, kiểm tra xA + yB = N. In YES và cặp đầu tiên tìm được, hoặc NO. Đạt 78/100 test (phần còn lại TLE).
#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;
// Vét cạn: thử mọi số bút x và số vở y
for (long long x = 0; x * A <= N; x++)
for (long long y = 0; x * A + y * B <= N; y++)
if (x * A + y * B == N) {
cout << "YES\n" << x << " " << y << "\n";
return 0;
}
cout << "NO\n";
return 0;
}
Sub 2: Duyệt x với kiểm tra chia hết — ~O(\min(N/A, B))~
Nếu (x, y) là nghiệm và x \ge B thì (x - B, y + A) cũng là nghiệm, nên nghiệm có x nhỏ nhất thỏa x < B. Duyệt x từ 0 đến min(N/A, B - 1) và kiểm tra (N - xA) chia hết cho B. Đạt 100/100 test.
#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;
// Nếu (x, y) là nghiệm thì (x - B, y + A) cũng là nghiệm, nên nghiệm có x nhỏ nhất thỏa x < B
// Duyệt x tăng dần, với mỗi x kiểm tra phần còn lại N - x*A có chia hết cho B không
for (long long x = 0; x * A <= N && x < B; x++) {
long long rem = N - x * A;
if (rem % B == 0) {
cout << "YES\n" << x << " " << rem / B << "\n";
return 0;
}
}
cout << "NO\n";
return 0;
}
Bình luận