TopCoder problem "DiscountCombination" used in TCO08 Round 1 (Division I Level One)



Problem Statement

    

There's a shoe store in which some models are popular, and some are not. In order to sell more unpopular models, the store introduced a system of discounts. Each discount works in the following way: if you buy an unpopular model for a cost of COST, then you can buy a popular model with a PERCENT% discount. However, the owner of the store is greedy, and therefore only discounts with PERCENTs equal to 1, 2 and 3 were introduced.

After it became obvious that such low discounts didn't work well, the store allowed people to apply more than one discount to the same pair of shoes. For example, you can buy three unpopular models, obtain three discounts and use all three to reduce the cost of the same popular model. When many discounts are applied to the same model, they are applied one after another. For example, if you apply 2% and 3% discounts to a model with cost 100, it's cost will be 0.98 * 0.97 * 100 = 95.06.

The available discounts are given in a String[] discounts, each element of which is formatted "COST PERCENT" (quotes for clarity). Different elements of discounts correspond to different unpopular models. You want to buy a popular model, which costs price. In order to reduce the model's cost, you can buy some unpopular models and obtain discounts from them, but you don't wish to buy the same unpopular model more than once. Return the minimum amount of money you need to spend in order to buy the desired popular model.

 

Definition

    
Class:DiscountCombination
Method:minimumPrice
Parameters:String[], int
Returns:double
Method signature:double minimumPrice(String[] discounts, int price)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9.
 

Constraints

-discounts will contain between 1 and 50 elements, inclusive.
-Each element of discounts will be formatted "COST PERCENT" (quotes for clarity), where COST and PERCENT are integers with no leading zeros.
-Each COST will be between 1 and 10,000,000, inclusive.
-Each PERCENT will be between 1 and 3, inclusive.
-price will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
{"1 1", "1 2", "1 3"}
100
Returns: 97.06
The best choice is to take 3% and 2% discounts. You pay 2 for unpopular models and reduce the cost of the popular model to 95.06.
1)
    
{"1000 1", "100 2", "10 3"}
33
Returns: 33.0
It doesn't make sense to use any discounts.
2)
    
{"10 2", "2 3", "6 2", "3 2", "3 1",
 "2 3", "9 3", "4 3", "2 3", "10 1"}

1000000000
Returns: 7.921497975738132E8
price is very large and discounts are cheap, so we use all of them.
3)
    
{"8667276 2",
 "3833771 1",
 "9208836 1",
 "5081823 3",
 "3367749 1",
 "4393655 2",
 "552508 1",
 "8648685 2",
 "3798496 2",
 "8104796 1"}
246918635
Returns: 2.415526549689562E8

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8641

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12011&pm=8641

Writer:

ivan_metelsky

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Greedy, Simple Math, Simple Search, Iteration