favorite We need a little bit of your help to keep things running, click on this banner to learn more

2020 USACO January Silver

Loan Repayment

Farmer John owes Bessie n gallons of milk. He has to give her the milk within k days. However, he doesn't want to give the milk away too quickly. On the other hand, he has to make forward progress on the loan, so he must give Bessie at least m gallons of milk each day.

Here is how Farmer John decides to pay back Bessie. He first picks a positive integer x. He then repeats the following procedure every day:

  • Assuming that Farmer John has already given Bessie g gallons, compute (ng) / x rounded down. Call this number y.
  • If y is less than m, set y to m.
  • Give Bessie y gallons of milk.

Determine the largest x such that if Farmer John follows the above procedure, Farmer John gives Bessie at least n gallons of milk after k days.


Three positive integers n (1n1012), k (1k1012), m (1m1012), satisfying k * m < n.


Output the largest positive integer x such that Farmer John will give Bessie at least n gallons using the above procedure.


For the first test case, when x = 2 Farmer John gives Bessie 5 gallons on the first day and m = 3 gallons on each of the next two days.

Time limit 1 second
Memory limit 128 MiB
Input example #1
10 3 3
Output example #1
Source 2020 USACO January Silver