Connection Status:
Competition Arena > BrokenStrings

BrokenStrings

TC China 08 - 1D · 2008-11-23 · by jthread

TC China 08 - 1D · 2008-11-23 · by jthread · Greedy
Class Name: BrokenStrings
Return Type: int
Method Name: buyStrings
Arg Types: (int, vector<string>)
Problem Statement

Problem Statement

You are a guitar player and you like to play your guitars, but unfortunately, you broke n strings. Therefore, you have to buy new strings to replace them, and you want to spend as little money as possible. For each brand of strings, you can choose to buy either a package of 6 strings, or 1 or more single strings.


You are given a String[] stringCosts, each element of which represents a single brand. Each element is formatted as "PACKAGE SINGLE" (quotes for clarity only), where PACKAGE is the price of a package of 6 strings and SINGLE is the price of a single string. Return the minimum amount of money required to buy at least n strings.

Notes

  • You are allowed to buy strings from different brands (it sometimes might even be needed to get the lowest price).
  • A package just contains 6 equal strings, so 1 package could be replaced by 6 single strings.

Constraints

  • n will be between 1 and 100, inclusive.
  • stringCosts will contain between 1 and 50 elements, inclusive.
  • Each element of stringCosts will be formatted as "PACKAGE SINGLE" (quotes for clarity only).
  • Each PACKAGE will be an integer between 0 and 1000, inclusive, with no extra leading zeroes.
  • Each SINGLE will be an integer between 0 and 1000, inclusive, with no extra leading zeroes.
Examples
0)
4
{"12 3",
 "15 4"}
Returns: 12

You can choose to buy 1 package of the first brand, or 4 single strings. The price you pay will be 12 in both cases.

1)
17
{"12 3"}
Returns: 36

The best option is to buy 3 packages (so you have 18 strings).

2)
7
{"10 3",
 "12 2"}
Returns: 12

Here you buy a package for 10, and another single string for 2 (from another brand) to get the lowest total price.

3)
73
{"59 25","54 84","33 71","75 21","67 39","75 37","16 57","83 17","58 37","77 71","2 77","59 50","80 76","46 58","89 22","99 4","28 43","98 11","51 47","11 55","46 66","29 38","61 79","91 76","33 79","19 34","92 83","51 69","95 66","24 6","1 22","81 42"}
Returns: 13
4)
91
{"64 85","23 7","46 78","75 18","13 81","98 0","32 94","14 95","48 96","22 33","19 85","48 7","83 75","23 68","22 80","18 96","25 88","50 72","50 73","73 49","31 52","62 26","51 5","44 96","18 48","52 63","54 1","32 40","94 87","32 1","36 93","56 66","95 29","77 55","59 88","55 36","41 71"}
Returns: 0

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

Coding Area

Language: C++17 · define a public class BrokenStrings with a public method int buyStrings(int n, vector<string> stringCosts) · 54 test cases · 2 s / 256 MB per case

Submitting as anonymous