Hướng dẫn giải của [200 đề thầy Đức] Bài 45: Bé Bi và những chiếc bút chì
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
Mô phỏng từng ngày: buổi sáng Bi dùng một bút, buổi tối nếu ngày là bội của m thì mẹ thêm một bút. Dừng khi Bi không còn bút để dùng vào buổi sáng; đáp án là số ngày liên tiếp trước ngày đó.
Chỉ viết 1 sub vì mô phỏng đã là cách giải trực tiếp, với n, m ≤ 100 chạy rất nhanh. Đạt 26/26 test.
Sub 1: Mô phỏng từng ngày — ~O(đáp án)~
Khởi tạo số bút là n. Với mỗi ngày d = 1, 2, ...: nếu không còn bút thì dừng; ngược lại giảm 1 bút (buổi sáng), và nếu d chia hết cho m thì tăng 1 bút (buổi tối). Đáp án là d − 1.
Kiểm tra với ví dụ: n = 2, m = 2 cho 3; n = 9, m = 3 cho 13.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m;
cin >> n >> m;
// Mô phỏng từng ngày: buổi sáng Bi dùng 1 bút, buổi tối nếu ngày là bội của m thì thêm 1 bút
long long pens = n;
long long day = 0;
while (true) {
day++;
if (pens == 0) break; // ngày này không còn bút để dùng
pens--; // buổi sáng dùng 1 bút (bút bị mất buổi chiều)
if (day % m == 0) pens++; // buổi tối mẹ thêm bút nếu ngày là bội của m
}
// Số ngày liên tiếp Bi còn bút là day - 1
cout << day - 1 << "\n";
return 0;
}
Bình luận