An Ever Growing Homework List
National Olympiad — Regional round (2023 season)
Submission name: tasks.cpp
Problem summary
A student starts with N tasks at H:M on January 1. She completes one task every P minutes, continuously. At every whole hour, Q new tasks are added if any tasks remain. If a completion empties the list exactly at a whole hour, she finishes before new tasks are added. Find her finishing day, hour and minute measured from January 1 at midnight.
Input
N H M P Q.
Output
Three integers: elapsed whole days since midnight, then hour and minute within the final day.
Constraints
1 ≤ N ≤ 10^9; 0 ≤ H ≤ 23; 1 ≤ M,P,Q ≤ 59; eventual completion is guaranteed.
Worked example
An independently prepared example for this explanation.
Input
9 20 45 15 2
Output
1 1 0
Solution analysis
- At completion number t, exactly t tasks have been solved. The number of earlier whole-hour additions is floor((M+tP−1)/60); subtracting one minute makes a simultaneous completion take priority. Completion occurs as soon as t−Q·floor((M+tP−1)/60) reaches N.
- This expression is not monotone, so an ordinary binary search is unsafe. Let g=gcd(P,60), L=60/g, and h=P/g. Advancing L completions always advances h whole hours, so the expression increases by the constant gain G=L−Qh.
- Write t=kL+r with 1≤r≤L. For each of at most 60 residues, compute the smallest nonnegative k reaching N, using ceiling division when G>0. If G≤0 only k=0 can be useful. Minimize t over the residues. In the sample t=17 gives 20:45+255 minutes=next day 01:00, where the final completion prevents another addition.
Why it works
Each positive completion index has a unique representation kL+r. The whole-hour floor increases by kh, so the computed affine expression is exact for that residue. The smallest feasible k is its earliest completion in that residue; minimizing over all residues gives the first time the list can empty.
Watch out. Do not binary search a function that can decrease at hour boundaries. Count additions strictly before the final completion. Use 64-bit arithmetic for large N.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
#include <numeric>
#include <limits>
using namespace std;
int main() {
long long n, hour, minute, period, added;
cin >> n >> hour >> minute >> period >> added;
long long divisor = gcd(period, 60LL);
long long length = 60 / divisor;
long long hours = period / divisor;
// One full residue cycle adds length completions and hours hourly additions.
long long gain = length - added * hours;
long long best = numeric_limits<long long>::max();
for (long long residue = 1; residue <= length; residue++) {
long long progress = residue - added * ((minute + residue * period - 1) / 60);
long long cycles = 0;
if (progress < n) {
if (gain <= 0) {
continue;
}
cycles = (n - progress + gain - 1) / gain;
}
best = min(best, cycles * length + residue);
}
long long finish = hour * 60 + minute + best * period;
cout << finish / 1440 << ' ' << finish / 60 % 24 << ' ' << finish % 60 << '\n';
}