Binary search on $X$. For the first subtask, we can check whether the number of gallons of milk that FJ gives is at least $N$ in $O(K)$ time. However, this does not suffice for full points.
How can we do better than $\Theta(K)?$ As the numbers in the statement are up to $10^{12},$ not $10^{18},$ this suggests that some sort of $\sqrt{N}$ factor is involved.
Suppose that we fix $X.$ Then $Y$ decreases over time. It turns out that if we process all transitions that leave $Y$ unchanged in $O(1)$ time, then our solution runs quickly enough! If there are more than $\sqrt {2N}$ distinct values of $Y$ then FJ definitely gives Bessie enough mlik because
It follows that our solution runs in $O(\sqrt N\log N)$ time.
Nick Wu's code:
#include <stdio.h> int valid(long long n, long long k, long long m, long long x) { long long g = 0; while(k > 0 && g < n) { long long y = (n - g) / x; if(y < m) { long long leftover = (n-g + m-1) / m; return leftover <= k; } long long maxmatch = n - x*y; long long numdays = (maxmatch - g) / y + 1; if(numdays > k) numdays = k; g += y * numdays; k -= numdays; } return g >= n; } int main() { freopen("loan.in", "r", stdin); freopen("loan.out", "w", stdout); long long n, k, m; scanf("%lld %lld %lld", &n, &k, &m); long long lhs = 1; long long rhs = 1e12; while(lhs < rhs) { long long mid = (lhs + rhs + 1) / 2; if(valid(n, k, m, mid)) { lhs = mid; } else { rhs = mid - 1; } } printf("%lld\n", lhs); }