USACO 2020Jan Silver - Loan Payment

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
zipdang04
Dạng bài
Điểm: 1 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bác John nợ Bessie \(N\) lít sữa \((1 \leq N \leq 10^{12})\), và phải trả cho Bessie trong \(K\) ngày. Tuy nhiên, bác không muốn trả nợ sữa quá sớm. Dù vậy, bác vẫn phải thúc đẩy tiến độ trả nợ, nên bác John phải trả Bessie ít nhất \(M\) lít sữa mỗi ngày \((1 \leq M \leq 10^{12})\).

Sau đây là cách bác John trả nợ Bessie. đầu tiên bác chọn ra một số nguyên dương \(X\). Sau đó bác lặp lại quy trình sau hằng ngày:

  1. Giả sử bác đã trả Bessie \(G\) lít sữa, làm tròn xuống \(\dfrac{N-G}{X}\). Gọi số này là \(Y\).
  2. Nếu \(Y < M\), đặt \(Y = M\).
  3. Trả cho Bessie \(Y\) lít sữa.

Hãy xác định số \(X\) lớn nhất sao cho nếu bác John thực hiện quy trình trên, bác sẽ trả Bessie ít nhất \(N\) lít sữa sau \(K\) ngày \((1 \leq K \leq 10^{12})\).

Dữ liệu đầu vào

  • Một dòng duy nhất chứa ba số nguyên dương tách nhau bằng một dấu cách \(N, K\) và \(M\) thỏa mãn \(K \times M < N\).

Định dạng đầu ra

  • Một dòng duy nhất in ra số \(X\) lớn nhất sao cho bác John sẽ trả ít nhất \(N\) lít sữa với quy trình trên.

Điểm số

  • Test 2-4 thỏa mãn \(K \leq 10^5\)
  • Test 5-11 không có điều kiện nào khác

Ví dụ

Ví dụ 1

Đầu vào 
10 3 3
Đầu ra 
2
Giải thích

Với ví dụ này, khi \(X = 2\), bác John trả Bessie 5 lít sữa trỏng ngày đầu và \(M=3\) lít trong vòng 2 ngày tiếp theo.

Lưu ý: nên sử dụng các kiểu dữ liệu số nguyên 64-bit (như long long trong C++)

Bình luận