# The Race

Is there any better way to do this problem?

``````// Question: http://www.usaco.org/index.php?page=viewproblem2&cpid=989

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

long long MaxToDistance(int MaxSpeed)
{
double e = (MaxSpeed-1) % 2;
return (1 + e/2)*MaxSpeed + MaxSpeed*((MaxSpeed-e-1)/2);
}

int DistanceToMax(long long Distance)
{
return floor((sqrt(Distance*2)+((0.125*sqrt(2))/sqrt(0.25))));
}

int FindSolution(long long MaxSpeed, long long RaceLength)
{

int SpedUpDistance = 0;
int RequiredSlowPeriod = 0;
int time = 0;

long long InitialDistance = MaxToDistance(MaxSpeed);

if (InitialDistance < RaceLength)
{
time = MaxSpeed;
SpedUpDistance = InitialDistance;
} else
{
return DistanceToMax(RaceLength);
}

for (int CurrentSpeed = time + 1;; CurrentSpeed++) {

SpedUpDistance += CurrentSpeed;
time++;

if (SpedUpDistance + RequiredSlowPeriod >= RaceLength) { return time; }
if (CurrentSpeed >= MaxSpeed) {
RequiredSlowPeriod += CurrentSpeed;
time++;
if (SpedUpDistance + RequiredSlowPeriod >= RaceLength) { return time; }
}

}

}

int main()
{
long long RaceLength, MaxSpeedAmount;
cin >> RaceLength >> MaxSpeedAmount;

for (int Index = 0; Index < MaxSpeedAmount; Index++)
{

//int MaxSpeed;
//cin >> MaxSpeed;
cout << FindSolution(Index,RaceLength) << "\n";

}

return 0;
}
``````

The edits are updates to the program that improved efficiency & accuracy. It currently is 2000% faster than the provided solution at returning a solution when the distance traveled to reach the max speed is greater than the race length (see DistanceToMax), and about 150-200% faster when doing all other equations.

(Benchmark, the input should be RaceDistance\tAmountOfMaxSpeed\nRaceDistance\tAmountOfMaxSpeed)