TopCoder problem "ThirdBuyDiscount" used in TCHS SRM 26 (Division I Level One)



Problem Statement

    

You want to buy a certain set of items. The shop offers you a discount percent discount on every third item you buy. Therefore, you want to purchase the items in an order that will minimize the total cost.

Given a int[] prices containing the prices of the desired items and an int discount, return the minimal amount of money you must have in order to buy all the items.

 

Definition

    
Class:ThirdBuyDiscount
Method:minCost
Parameters:int[], int
Returns:double
Method signature:double minCost(int[] prices, int discount)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-discount will be between 0 and 100, inclusive.
-prices will contain between 0 and 50 elements, inclusive.
-Each element of prices will be between 0 and 2147483647, inclusive.
 

Examples

0)
    
{50, 20, 30, 17, 100}
10
Returns: 207.0
One of the possible optimal sequences is {20, 30, 100, 17, 50}. So, the total cost is 20 + 30 + 0.9 * 100 + 17 + 50 = 207.
1)
    
{1,2,3,4,5,6,7}
100
Returns: 15.0
The discount is 100%, a fantastic bargain for the consumer. Make the item with price 6 the third item you buy, and the item with price 7 the sixth.
2)
    
{100,40,23,592,582,19435739,204857,0}
0
Returns: 1.9641933E7
There is no discount, so the total cost is always equal to the sum of all the original prices.
3)
    
{999,111,888,1238,52009,419,0,0,43,0,11,4,2,348,10039586,1000000,203985157}
37
Returns: 1.355019587E8
4)
    
{100,304,50607,2024,6046,708}
75
Returns: 17299.25
5)
    
{1}
50
Returns: 1.0
6)
    
{}
100
Returns: 0.0

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10650&pm=6745

Writer:

gevak

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Greedy, Sorting