For this problem (USACO), I found the fastest speed n that can be attained and reasoned that the optimal solution will have speeds 1 2 3 … n n-1 n-2. … x as a subsequence of the speed sequence (ie Bessie will at some point speed up to n then back down to x at the end). But when I test my code, it doesn’t pass test cases 5+ (my values are larger than expected) . Where did I make a mistake?
#include <bits/stdc++.h>
using namespace std;
ssize_t sum(ssize_t a, ssize_t b){
return (b*(b+1))/2 - (a*(a-1))/2;
}
ssize_t fastest_speed(ssize_t K, ssize_t X){
for (ssize_t n=1;n<K; ++n){
if (K <= sum(1, n+1) + sum(X+1, n)){
return n;
}
}
return K;
}
int main() {
//freopen(“race.in”, “r”, stdin);
//freopen(“race.out”, “w”, stdout);
ssize_t K,N; cin >> K >>N;
for (size_t i=0; i<N; ++i){
ssize_t X; cin >> X;
ssize_t n = fastest_speed(K,X);
ssize_t leftovers = K- sum(1, n) - sum(X,n-1);
if (leftovers <=0){
cout << n + (n-X) << “\n”;
}
else if (leftovers %n == 0){ //leftovers is a multiple of n, make Bessie run at speed n to cover //leftovers
cout << n + (n-X) + leftovers/n << “\n”;
}
else{ // make Bessie run at speed n as much as possible, then make her run at a speed <n to cover rest of distance
cout << n + (n-X) + leftovers/n + 1 << “\n”;
}
}
}