Holiday Costing
Time limit1sMemory limit128 MB
For each stay length at a hotel, choose one stay/pay deal, repeated as allowed, to minimize the nights you pay for.
- Level
Medium4 of 10
- Topics
- Brute force, Implementation, Greedy, Math
- Solved
- No attempts yet
Problem
Resort hotels often offer "stay/pay" deals: after you stay a certain number of nights, some of those nights become free. For example, in a stay 8 / pay 7 deal, staying 8 nights means you pay for only 7 (one night is free), and staying 9 nights means you pay for 8.
These deals can accumulate. For example, a stay 6 / pay 4 deal that may be repeated up to three times also creates an effective stay 12 / pay 8 deal and a stay 18 / pay 12 deal. A single hotel may offer several stay/pay deals, but different deals cannot be combined with one another.
Write a program that finds the best price for a given length of stay, choosing the single most advantageous deal (repeated when allowed) for that stay.
Input
The input contains several data sets, one for each hotel.
The first line for a hotel is the hotel name: up to 20 characters, possibly including spaces.
Next come between 0 and 10 stay/pay deals, one per line. Each deal is three integers in the range 1 to 99: the stay length, the pay length, and how many times the deal may be repeated. The list of deals ends with a line 0 0 0.
After the deals comes a list of stay lengths, one integer per line, each in the range 1 to 99. This list ends with a line containing a single 0, which is not processed.
The whole sequence of hotels ends with a line containing a single #.
Output
For every stay length in the input, print one line giving the minimum number of nights that must be paid for. This minimum is made up of standard nights (you pay for every night you stay) together with at most one stay/pay deal, repeated as many times as allowed when that helps.
Print each line in exactly this format:
Stay <n> nights at <name>, pay <p>.
where <n> is the number of nights stayed, <name> is the hotel name, and <p> is the minimum number of nights paid for. Use night (singular) when <n> is 1 and nights otherwise, matching the sample output.