USACO 2020 January Contest Bronze Division - Race

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can brute force the maximum speed and then do a bit of math based on observing that we need a certain amount of seconds to get there, then stay there for a while and then come back to the final speed.

Source codes

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

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

int main()
{
    ifstream cin("race.in");
    ofstream cout("race.out");

    long long k, n;
    cin >> k >> n;

    for(; n; n--)
    {
        long long maxspeed;
        cin >> maxspeed;
        long long totaltime = k;

        for(int mx = 1; mx <= 100000; mx++)
        {
            long long mindist = 1LL * mx * (mx+1) / 2;
            long long cnt = mx;
            if(mindist > k)
                continue;
            if(mx > maxspeed)
            {
                long long sum = (mx - 1) * mx / 2 - 1LL * maxspeed * (maxspeed-1) / 2;
                cnt += (mx - maxspeed);
                if(mindist + sum <= k)
                {
                    long long tmp = (k - mindist - sum + mx - 1) / mx;
                    totaltime = min(totaltime, tmp+cnt);
                }
            }
            else
            {
                long long tmp = (k - mindist + mx - 1) / mx;
                totaltime = min(totaltime, tmp+cnt);
            }
        }
        cout << totaltime << '\n';
    }
    return 0;
}