Hướng dẫn giải của [200 đề thầy Đức] Bài 62: Uống coca
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
Mập có $a$ vỏ chai, sẽ kiếm thêm $b$ vỏ chai, và cần $c$ vỏ chai để đổi lấy một chai cô ca mới. Uống xong chai đó, Mập lại có thêm một vỏ chai. Tìm số chai cô ca nhiều nhất Mập có thể uống.
Sub 1: Mô phỏng từng lần đổi — ~O(a + b)~
Gộp $x = a + b$ vỏ chai. Khi $x \ge c$, bán $c$ vỏ để mua một chai, uống xong $x$ giảm $c$ rồi tăng $1$. Lặp lại đến khi không còn đủ $c$ vỏ. Vì $x \le 2000$ nên số bước rất ít. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b, c;
cin >> a >> b >> c;
long long x = a + b; // tổng số vỏ chai có
long long drunk = 0;
// Mô phỏng: đủ c vỏ thì bán c vỏ mua 1 chai, uống xong được lại 1 vỏ.
while (x >= c) {
x -= c; // bán c vỏ để mua 1 chai
drunk++; // uống chai đó
x += 1; // được 1 vỏ chai mới
}
cout << drunk << "\n";
return 0;
}
Sub 2: Công thức — ~O(1)~
Mỗi lần mua, số vỏ chai giảm đúng $c - 1$. Xuất phát từ $x$ vỏ, phải có ít nhất $c$ vỏ mới mua được, nên số lần mua là số nguyên lớn nhất $k$ thỏa $x - (k-1)(c-1) \ge c$, tức đúng bằng $\lfloor (x-1)/(c-1) \rfloor$ khi $x \ge 1$.
Ví dụ: $9, 0, 3$ cho $x = 9$, $\lfloor 8/2 \rfloor = 4$. Ví dụ: $5, 5, 2$ cho $x = 10$, $\lfloor 9/1 \rfloor = 9$.
Bẫy cần chú ý: khi $x = 0$ thì không mua được chai nào, cần xét riêng để tránh tính $\lfloor -1/(c-1) \rfloor$.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b, c;
cin >> a >> b >> c;
long long x = a + b; // tổng số vỏ chai có
// Mỗi lần mua một chai, số vỏ giảm đi c - 1 (bán c vỏ, được lại 1 vỏ).
// Số lần mua tối đa là số bước để x giảm xuống dưới c:
// có (x - 1) / (c - 1) lần khi x >= 1 (x - 1 chia hết lấy phần nguyên).
if (x == 0)
cout << 0 << "\n";
else
cout << (x - 1) / (c - 1) << "\n";
return 0;
}
Bình luận