## ECOO '13 R1 P4 - Coupon Day

View as PDF

Points: 10 (partial)
Time limit: 13.0s
Memory limit: 256M

Problem type

It's coupon day at Panther Redirect. Customers have been collecting coupons all year, and today is the day they get to use them. During this special sale day, there's a limit of purchases per customer and they are allowed to bring up to coupons with them to the counter. Each coupon can be applied to a maximum of item, and each item can have a maximum of coupon applied to it. The cashier will scan the price codes and the coupons and will help the customers decide how to use their coupons to maximize their savings.

There are coupon types available. The , , and coupons entitle the customers to a flat discount before tax is applied (if the item is worth less than the coupon, they get it for free). The and coupons entitle the customer to a percentage discount before tax. The TAX coupon entitles the customer to have the item without paying any HST. Finally, the BOGO coupon (maximum of per customer) allows the user to buy one item at full price and get a second item of equal or lesser price for free. Note that neither of the items involved in the BOGO can have other coupons applied to them. The HST is calculated separately on the unrounded price of each item after the coupon is applied. The after tax price for each item is rounded to the nearest cent after tax has been applied. These final prices are added together to get the total purchase price.

The input will contain test cases. The first line of each test case contains an integer indicating the number of purchase items . This is followed by the prices in dollars and cents, each on a separate line . The next line contains an integer , indicating the number of coupons . This is followed by the coupon names, each on a separate line.

Write a program that finds the best way to apply the coupons for each customer (the best way being the way that yields the lowest total price according to the rules and restrictions applied above) and then states the final price exactly as shown in the sample output below, always showing two decimal places. The program must terminate within the time limit set out in the general contest rules.

#### Sample Input

3
74.54
19.8
69.99
10
BOGO
20%
$50 BOGO 20% TAX 20%$5
$5 10% 9 93.43 13.69 17.02 1.94 6.52 65.55 8.36 83.2 0.11 10$5
$10$10
TAX
$5 20% BOGO BOGO TAX BOGO 4 88.17 43.18 67.14 2.51 5 20% 20%$50
TAX
$50 #### Sample Output The best price is$84.23
The best price is $184.51 The best price is$101.35

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

• commented on Aug. 6, 2021, 9:32 p.m. edited

You can do the second one with $184.07 by: •$93.43- BOGO
• $83.2 (skip) •$65.55- 20 percent off
• $17.02- BOGO •$13.69 (skip)
• $8.36- 10 dollars off •$6.52- 10 dollars off
• $1.94- 5 dollars off •$0.11- 5 dollars off

multiply by 1.13 at the end = 184.0657 = 184.07

EDIT: my bad used multiple BOGOs

• commented on Oct. 14, 2014, 10:01 a.m.

It will be fixed eventually. Please look at the official statement for now.

• commented on June 14, 2015, 9:58 a.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on June 14, 2015, 11:41 a.m. edited

And it will be, eventually. Typesetting ECOO problems takes time, a limited resource which we're instead choosing to dedicate to improving this site and organizing contests. If you'd like, you can file a ticket for this problem, or even better: format the statement yourself, so that others may benefit as well (and not have to wait an indefinite time until we get around to it).

• commented on April 24, 2016, 10:49 p.m.

Well, I've managed to make the statement readable. It should be fine for now.