USACO 2020 January Contest Silver Division - Loan Repayment

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

You can binary search for x, and then simulate giving milk (no need for another bin. search), with skipping over chunks to only have iterations for distinct values (time complexity \(O(n)\) to \(O(\sqrt(2 \cdot n))\).

hint needed: in addition to last part where it is repeating Ms, have to process in chunks the repeated quotient from division (as it is floor division), until it crosses over the floor boundary and moves to next ex. 62 61 60 | 59 58 57 | etc.

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, k, m;

ll ok(ll x)
{
    ll day = 0;
    ll sum = 0;
    while(day < k)
    {
        ll ratio = (n-sum) / x;
        ll remainder = (n-sum) % x;
        if(ratio < m)
        {
            sum += (k-day) * m;
            break;
        }
        ll daysratio = 1 + remainder/ratio;
        sum += min(k-day, daysratio) * ratio;
        day += min(k-day, daysratio);
    }
    return (sum >= n);
}
int main()
{
    ifstream cin("loan.in");
    ofstream cout("loan.out");

    cin >> n >> k >> m;

    ll st = 1;
    ll dr = (1LL<<40);
    ll ans = 1;
    while(st <= dr)
    {
        ll mid = (st + dr) / 2;
        if(ok(mid))
            ans = mid, st = mid + 1;
        else
            dr = mid - 1;
    }
    cout << ans;
    return 0;
}