Hướng dẫn giải của Câu 1 (đề Bình Dương 2021)
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 tổng lớn nhất không vượt N có dạng i·A + j·B với i, j là số nguyên không âm (số hộp loại A và loại B). Do N, A, B ≤ 1000 nên có thể thử nhiều cách.
Sub 1: Vét cạn mọi cặp (i, j) — ~O(N^2)~
Thử mọi số hộp A (i) và hộp B (j) sao cho tổng không vượt N, giữ tổng lớn nhất. Đạt 20/20 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;
// Vét cạn: thử mọi số hộp loại A (i) và loại B (j), giữ tổng lớn nhất không vượt N
long long best = 0;
for (long long i = 0; i * A <= N; i++) {
for (long long j = 0; i * A + j * B <= N; j++) {
best = max(best, i * A + j * B);
}
}
cout << best << "\n";
return 0;
}
Sub 2: Cố định số hộp A, lấy tối đa hộp B — ~O(N/A)~
Với mỗi số hộp A là i, phần còn lại N - i·A được lấp bằng số hộp B tối đa là floor((N - i·A)/B). Lấy max theo mọi i. Đạt 20/20 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;
// Cố định số hộp loại A = i, phần còn lại (N - i*A) lấy tối đa số hộp loại B
// Tổng = i*A + floor((N - i*A)/B)*B, lấy max theo mọi i
long long best = 0;
for (long long i = 0; i * A <= N; i++) {
long long rest = N - i * A;
long long total = i * A + (rest / B) * B;
best = max(best, total);
}
cout << best << "\n";
return 0;
}
Bình luận