Hướng dẫn giải của KS Câu 2: Đổ sữa
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
Cho X, Y (X < Y) là dung tích hai ca và M là dung tích yêu cầu (M ≤ 1000). Có thể đổ đầy ca rồi đổ vào bình nhiều lần. Tìm lượng sữa lớn nhất không vượt quá M.
Sub 1: Vét cạn, thử mọi số lần đổ — ~O(M^2 / (XY))~
Thử mọi số lần a đổ ca X và b đổ ca Y sao cho aX + bY ≤ M, lấy tổng lớn nhất.
Kết quả chấm: 10/10
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long x, y, m;
cin >> x >> y >> m;
long long best = 0;
// Vet can: thu moi so lan a do binh X va b do binh Y, lay tong lon nhat khong vuot M
for (long long a = 0; a * x <= m; a++)
for (long long b = 0; a * x + b * y <= m; b++)
best = max(best, a * x + b * y);
cout << best << "\n";
return 0;
}
Sub 2: Quy hoạch động đánh dấu — ~O(M)~
Đánh dấu reach[s] = true nếu có thể đổ đúng s lít bằng cách cộng X hoặc Y vào tổng trước đó. Đáp án là s lớn nhất trong khoảng [0, M] có reach[s] đúng.
Kết quả chấm: 10/10
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x, y, m;
cin >> x >> y >> m;
// reach[s] = true neu co the do dung s lit sua bang cac ca X, Y (do nhieu lan)
vector<bool> reach(m + 1, false);
reach[0] = true;
for (int s = 1; s <= m; s++)
reach[s] = (s >= x && reach[s - x]) || (s >= y && reach[s - y]);
// Dap an la tong lon nhat co the do ma khong vuot M
int best = 0;
for (int s = 0; s <= m; s++)
if (reach[s]) best = s;
cout << best << "\n";
return 0;
}
Bình luận