Per-Second Telephone Tariff
National Olympiad — Regional round (2014 season)
Submission name: tariff.cpp
Problem summary
A customer starts with F free minutes. Calls wholly covered by the remaining allowance consume their duration rounded up to whole minutes. If the allowance ends during a call, the remaining seconds cost one lev each. Find the total cost of the ordered calls.
Input
N and F; then N pairs m s, the whole minutes and seconds of each call.
Output
The total integer cost in leva.
Constraints
0 ≤ N,F ≤ 1000; 0 ≤ m ≤ 1000; 0 ≤ s ≤ 59.
Worked example
An independently prepared example for this explanation.
Input
4 10 1 0 0 5 3 40 4 12
Output
12
Solution analysis
- For a call of duration seconds, remaining free capacity is 60*F seconds. If the call fits, subtract ceil(seconds/60) free minutes.
- If it does not fit, charge seconds−60*F, then set F to zero. All later call seconds are charged. A zero-duration call consumes no free minutes.
- In the sample, the first three calls consume 1,1,4 free minutes. Four remain for the last 4:12 call, leaving 12 paid seconds.
Why it works
Before each call F is exactly the unused whole-minute allowance. A covered call uses its prescribed rounded-up minutes. An uncovered call consumes the entire allowance and charges precisely the seconds after it expires. These updates preserve the allowance and accumulated cost invariants through every call.
Watch out. Round only covered calls, not every duration before charging. Free minutes can end in the middle of a call.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int n, freeMinutes;
cin >> n >> freeMinutes;
long long cost = 0;
for (int i = 0; i < n; i++) {
int minutes, seconds;
cin >> minutes >> seconds;
int duration = 60 * minutes + seconds;
// Round only calls wholly covered by the free allowance.
if (duration <= 60 * freeMinutes) {
freeMinutes -= (duration + 59) / 60;
} else {
cost += duration - 60 * freeMinutes;
freeMinutes = 0;
}
}
cout << cost << '\n';
}