List editorial
Trong nhà mèo Tôm ban đầu có \(N\) hạt thóc. Vụ mùa đến, mèo Tôm dành một ngày đi thu hoạch thóc mang về nhà rồi ngày hôm sau sang nhà chó Spike chơi, mèo Tôm cứ lặp đi lặp lại các ngày như vậy. Chuột Jerry biết được lịch trình của mèo Tôm nên cứ đến ngày mèo Tôm sang nhà chó Spike chơi thì chuột Jerry sang nhà mèo Tôm lấy đi một nửa số thóc mà ngày hôm trước mèo Tôm thu hoạch được (nếu số thóc mèo Tôm thu hoạch là số lẻ - giả sử là \(X\) thì số thóc chuột Jerry lấy là một nửa của \((X - 1)\).
Biết rằng, mèo Tôm lần đầu tiên sẽ thu hoạch được \(K\) hạt thóc, và mỗi lần thu hoạch sau đó sẽ bị giảm 1 hạt thóc (lần thứ hai thu hoạch \(K - 1\) hạt thóc, lần thứ ba thu hoạch \(K - 2\) hạt thóc,…) và đến khi thu hoạch được 1 hạt thóc thì sẽ không bị giảm nữa.
Mèo Tôm là một con mèo rất kém tính toán, mèo Tôm muốn biết sau ít nhất bao nhiêu ngày thì trong nhà mèo Tôm có tối thiểu \(M\) hạt thóc. Em hãy lập trình để tính toán giúp mèo Tôm.
Yêu cầu:
Cho ba số tự nhiên \(N,M\) và \(K\). Hỏi thời điểm đầu tiên mà ở trong nhà mèo Tôm có tối thiểu \(M\) hạt thóc.
Dữ liệu:
Nhập vào ba dòng tương ứng là ba số tự nhiên \(N,M\) và \(K\).
\((1 ≤ N,M,K ≤ 10^9 ; M > N).\)
Kết quả:
Ghi ra một số là kết quả của bài toán.
Ví dụ:
| Nhập vào | Xuất ra | Giải thích |
|---|---|---|
| 6 22 10 |
5 | Ngày đầu tiên mèo Tôm mang về 10 hạt thóc \(\to\) có 10 + 6 = 16 hạt thóc. Ngày thứ 2, chuột Jerry lấy 5 hạt thóc \(\to\) còn 16 − 5 = 11 hạt thóc. Ngày thứ 3, mèo Tôm mang về 9 hạt thóc \(\to\) có 20 hạt thóc. Ngày thứ 4, chuột Jerry lấy 4 hạt thóc \(\to\) có 16 hạt thóc. Ngày thứ 5, mèo Tôm mang về 8 hạt thóc \(\to\) có 24 hạt thóc. Vậy ngày thứ 5 trong nhà mèo Tôm đã có tối thiểu 22 hạt thóc. |
| 5 8 2 |
5 | Ngày đầu tiên mèo Tôm mang về 2 hạt thóc \(\to\) có 5+2 = 7 hạt thóc. Ngày thứ 2, chuột Jerry lấy 1 hạt thóc \(\to\) còn 7−1 = 6 hạt thóc. Ngày thứ 3, mèo Tôm mang về 1 hạt thóc \(\to\) có 7 hạt thóc. Ngày thứ 4, chuột Jerry lấy 0 hạt thóc \(\to\) có 7 hạt thóc. Ngày thứ 5, mèo Tôm mang về 1 hạt thóc \(\to\) có 8 hạt thóc. Vậy ngày thứ 5 trong nhà mèo Tôm đã có tối thiểu 8 hạt thóc |
Chấm điểm:
• Nếu chương trình chạy đúng những trường hợp \(N,M,K ≤ 10^4\) , thí sinh sẽ được 60 điểm;
• Nếu chương trình chạy đúng những trường hợp \(N,M,K ≤ 10^9\) , thí sinh sẽ được 100 điểm.
Không có ý kiến tại thời điểm này.