Hướng dẫn giải của [200 đề thầy Đức] Bài 116: Đong gạo
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 đong đúng ~N~ kg gạo bằng bịch 5 kg và bịch 3 kg sao cho số bịch ít nhất. Nếu không thể đong đúng thì in -1.
Sub 1: Vét cạn mọi cặp (x, y) — ~O(N^2)~
Thử mọi số bịch 5 kg ~x~ và mọi số bịch 3 kg ~y~, nếu ~5x + 3y = N~ thì cập nhật số bịch ~x + y~ nhỏ nhất. Đạt 20/20 test (N nhỏ nên chạy kịp).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// Vét cạn: thử mọi cặp (x bịch 5kg, y bịch 3kg)
int ans = -1;
for (int x = 0; x <= n / 5; x++) {
for (int y = 0; y <= n / 3; y++) {
if (5 * x + 3 * y == n) {
if (ans == -1 || x + y < ans) ans = x + y;
}
}
}
cout << ans << "\n";
return 0;
}
Sub 2: Chỉ duyệt số bịch 5 kg — ~O(N)~
Chỉ cần duyệt ~x~ (số bịch 5 kg). Với mỗi ~x~, phần gạo còn lại ~N - 5x~ phải chia hết cho 3, khi đó số bịch 3 kg là ~(N - 5x) / 3~. Lấy tổng số bịch nhỏ nhất. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// Chỉ cần duyệt số bịch 5kg (x), phần còn lại (n - 5x) phải chia hết cho 3
int ans = -1;
for (int x = 0; x * 5 <= n; x++) {
int rest = n - 5 * x;
if (rest % 3 == 0) {
int total = x + rest / 3; // số bịch = x + số bịch 3kg
if (ans == -1 || total < ans) ans = total;
}
}
cout << ans << "\n";
return 0;
}
Bình luận