TopCoder problem "VolumeDiscount" used in SRM 276 (Division I Level One , Division II Level Two)



Problem Statement

    

When a customer buys large quantities of a product, frequently the seller will offer a volume discount. For instance, one unit might cost 10 dollars, but might be offered in packages of 5 for 45 dollars. In such a case, it always makes sense buy the bulk lots to save money. In some other cases, however, it might not always make sense. Suppose a single unit were on sale for 8 dollars. In such a case, purchasing single units would be less expensive than purchasing a 5-pack.

You are given a String[] priceList describing the number of units available in each bundle, and the cost of the bundle. Each element is of the form "units cost" (quotes added for clarity). You are also given an int quantity, the number of units you wish to purchase.

Return an int indicating the best possible cost to purchase at least the desired quantity of units.

 

Definition

    
Class:VolumeDiscount
Method:bestDeal
Parameters:String[], int
Returns:int
Method signature:int bestDeal(String[] priceList, int quantity)
(be sure your method is public)
    
 

Constraints

-priceList will contain between 1 and 5 elements, inclusive.
-Each element of priceList will be formatted as described in the problem statement.
-units will be an integer between 1 and 99, inclusive, with no leading zeroes
-cost will be an integer between 1 and 999, inclusive, with no leading zeroes.
-No two values of units will be the same.
-quantity will be between 1 and 99, inclusive.
 

Examples

0)
    
{"1 10", "5 45"}
10
Returns: 90
The first example suggested in the problem statement.
1)
    
{"1 8", "5 45"}
10
Returns: 80
The second example suggested in the problem statement.
2)
    
{"99 913", "97 173", "50 464", "80 565"} 	
18
Returns: 173
Here, every package has more units than we need, so we pick the cheapest one.
3)
    
{"2 272","1 166","10 993"}
81
Returns: 8110

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8073&pm=5945

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Recursion