Connection Status:
Competition Arena > VolumeDiscount

VolumeDiscount

SRM 276 · 2005-12-08 · by brett1479

SRM 276 · 2005-12-08 · by brett1479 · Brute Force, Recursion
Class Name: VolumeDiscount
Return Type: int
Method Name: bestDeal
Arg Types: (vector<string>, int)
Problem Statement

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.

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)
{"99 577", "97 796", "50 449"}
50
Returns: 449
4)
{"99 577", "97 796", "50 449"}
21
Returns: 449

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

Coding Area

Language: C++17 · define a public class VolumeDiscount with a public method int bestDeal(vector<string> priceList, int quantity) · 122 test cases · 2 s / 256 MB per case

Submitting as anonymous