Connection Status:
Competition Arena > DiscountCombination

DiscountCombination

TCO08 Round 1 · 2008-01-21 · by ivan_metelsky

TCO08 Round 1 · 2008-01-21 · by ivan_metelsky · Greedy, Simple Math, Simple Search, Iteration
Class Name: DiscountCombination
Return Type: double
Method Name: minimumPrice
Arg Types: (vector<string>, int)
Problem Statement

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.

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
4)
{
"8432173 1",
"7599140 3",
"1225549 2",
"3530111 1",
"1351029 1",
"1412319 1",
"2974671 1",
"5967097 2",
"2126987 1",
"719988 3",
"3379965 1",
"65883 1",
"8355170 2",
"7526574 2",
"369472 2",
"6154515 1",
"7462251 3",
"1714858 2",
"2827811 1",
"220798 1",
"1478235 2",
"2619159 2",
"1168789 3",
"9843628 2",
"6457960 2",
"9124725 3",
"1173667 1",
"243871 2",
"582412 3",
"6575705 3",
"2494017 3",
"410508 1",
"7614784 1",
"3305895 3",
"7792642 2",
"4268312 2",
"6969666 1",
"8992470 2",
"1102043 3",
"7779995 2",
"7683279 1",
"3854767 3",
"6186980 2",
"4293344 1",
"3141480 1",
"6029582 3",
"1492118 1",
"3170018 1",
"450961 1",
"5297823 3"
}
160807949
Returns: 1.3186114174683641E8

Submissions are judged against all 261 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DiscountCombination with a public method double minimumPrice(vector<string> discounts, int price) · 261 test cases · 2 s / 256 MB per case

Submitting as anonymous