A Contest Strategy
National Olympiad — Municipal round (2018 season)
Submission name: contest.cpp
Problem summary
A contest has n problems and lasts t hours. Peter spends the entire first hour solving f familiar problems, then needs x minutes for each remaining problem. Determine whether he finishes early, exactly on time, or late. In the late case, also report how many problems remain unsolved at the deadline.
Input
Four integers n, t, f, x.
Output
If early, print YES and the spare minutes on the next line. If exactly on time, print EXACT!. Otherwise print NO, missing minutes, and unfinished problems on three lines.
Constraints
5 ≤ n ≤ 100; 1 ≤ f < n; 2 ≤ t ≤ 24; 10 ≤ x ≤ 60.
Worked example
An independently prepared example for this explanation.
Input
12 5 7 45
Output
YES 15
Solution analysis
- After the compulsory first hour, there are (t−1)·60 minutes available and n−f problems left. Completing those problems would take (n−f)·x minutes.
- Compare the required minutes with the available minutes. Their difference gives spare or missing time. When time is insufficient, integer division available/x counts how many of the remaining problems can be completed.
- For n=12,t=3,f=7,x=45, the last five problems require 225 minutes but only 120 remain. Peter lacks 105 minutes and finishes only two of those five problems, leaving three unsolved.
Why it works
The first hour is fixed by the strategy. Every later completed problem uses exactly x minutes, so the required total and the floor of available/x exactly model completion and the deadline. Comparing those totals gives all three output cases.
Watch out. Always reserve the full first hour, even if the familiar problems take less time. A partially solved problem still counts as unfinished.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int n, t, f, x;
cin >> n >> t >> f >> x;
int remaining = n - f;
// The strategy reserves the entire first hour for familiar problems.
int available = (t - 1) * 60;
int required = remaining * x;
if (required < available) {
cout << "YES\n" << available - required << '\n';
} else if (required == available) {
cout << "EXACT!\n";
} else {
cout << "NO\n";
cout << required - available << '\n';
cout << remaining - available / x << '\n';
}
}