PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Le Duc Minh
Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Ann has X energy, and in each second can either run (if she has more than 0 energy) and lose 1 energy, or rest (and gain 1 energy, if she has less than X). She cannot have more than X energy. It takes her R minutes of running to finish a race - is there some sequence of running and resting which lets her finish the race within M minutes?
EXPLANATION:
Before anything else, to simplify calculation, convert R and M to seconds by multiplying them by 60.
What is the least amount of time within which Ann can run for R seconds?
She can first run for X seconds, and expend all the energy she initially has. After that, running for one second requires two seconds of time - one to rest and gain 1 energy, and then one to actually run. This is optimal.
Proof
The strategy described above is, in simpler words, to run when Ann has positive energy and rest when she has none. Optimality can be proved using an exchange argument.
Consider any optimal strategy where Ann has positive energy at some time, but decides to rest.
We can then find a time i such that Ann has positive energy at time i, rests at time i, and runs at time i+1.
Exchange her actions at these two times - i.e, suppose she runs at time i and rests at time i+1. Keep all other actions the same.
The amount of time she ran is exactly the same in both cases, and her remaining energy is either the same (if her energy at time i was < X), or greater (if her energy at time i was X). Thus, exchanging the actions gives a solution which is not worse than the original.
tl;dr, the strategy described of always running when possible is no worse than any other optimal solution.
So,
- If R\leq X, she needs exactly R seconds
- If R > X, she needs X + 2*(R-X) seconds
Simply compute this number, and check whether it is \leq M.
Be wary of overflow!
Note that the constraints have R,M \leq 10^9, and converting them to seconds will result in integers upto 6*10^{10}. This will not fit in a 32-bit integer, so make sure you use the correct data type.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
SOLUTIONS:
Setter's Solution (C++)
#include<bits/stdc++.h>
using namespace std;
int q;
long long x, t, m;
int main() {
cin >> q;
while (q--) {
cin >> x >> t >> m;
// Convert to seconds
t *= 60;
m *= 60;
long long time_needed = min(x, t);
if (x < t) {
time_needed += (t - x) * 2;
}
if (time_needed <= m) {
cout<< "YES\n";
}
else {
cout << "NO\n";
}
}
}
Tester's Solution (C++)
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
int main(){
fastio;
int tests;
cin>>tests;
while(tests--){
long long int x, t, m;
cin>>x>>t>>m;
t *= 60;
m *= 60;
long long int curr = min(m, x);
m -= curr;
curr += m / 2;
if(curr >= t) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
Editorialist's Solution (Python)
q = int(input())
for _ in range(q):
x, t, m = map(int, input().split())
t *= 60
m *= 60
if m < t:
print('NO')
elif t <= x:
print('YES')
elif x + 2*(t-x) <= m:
print('YES')
else:
print('NO')
