SD Cards
Autumn Tournament (2020)
Submission name: sdcards.cpp
Problem summary
Store N match recordings on SD cards. Recordings may be split freely, and a card may hold parts of several matches. A 240-minute card costs 10.90 leva and a 180-minute card costs 9.15 leva. Find the cheapest sufficient collection.
Input
N, followed by N pairs of integers: hours and minutes of each recording.
Output
The minimum price in leva with exactly two digits after the decimal point.
Constraints
1 ≤ N ≤ 4; 0 ≤ hours ≤ 24; 0 ≤ minutes ≤ 59.
Worked example
Original statement, example 1.
Input
2 2 06 1 11
Output
10.90
Solution analysis
- Because recordings may be split, only their total length T matters. Convert each duration to minutes and each price to integer stotinki.
- Enumerate the number x of 240-minute cards from 0 through ceil(T/240). For each x, cover the remaining minutes with y = ceil(max(0, T − 240x)/180) smaller cards. Minimize 1090x + 915y.
- In the example T = 126 + 71 = 197. Two smaller cards cost 18.30, while one larger card costs 10.90 and holds all recordings.
Why it works
For a fixed number x of larger cards, the chosen y is the least number of smaller cards that provides enough capacity, hence is cheapest for that x. Counts above ceil(T/240) are more expensive than that many larger cards alone. Thus the enumeration includes an optimal collection.
Watch out. Use integer prices to avoid rounding errors. A zero-length total needs no cards.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int main(){
int n;
cin>>n;
int total=0;
for(int i=0;i<n;++i){
int hours,minutes;
cin>>hours>>minutes;
total+=60*hours+minutes;
}
int best=1000000000;
for(int large=0;large<=(total+239)/240;++large){
int remaining=max(0,total-240*large);
int small=(remaining+179)/180;
best=min(best,1090*large+915*small);
}
// Print the cents as two digits, even when the last digit is zero.
cout<<best/100<<'.'<<setw(2)<<setfill('0')<<best%100<<'\n';
}