2020 USACO January Silver
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 (n − g) / 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 (1 ≤ n ≤
1012), k (1 ≤ k ≤
1012), m (1 ≤ m ≤
1012), 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.
10 3 3