Statistics

Problem Statement for "BrokenStrings"

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.

Definition

Class:
BrokenStrings
Method:
buyStrings
Parameters:
int, String[]
Returns:
int
Method signature:
int buyStrings(int n, String[] stringCosts)
(be sure your method is public)

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

  1. 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.

  2. 17

    {"12 3"}

    Returns: 36

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

  3. 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.

  4. 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

  5. 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

  6. 77

    {"52 55","48 58","56 34","87 3","56 39","81 96","4 33","42 74","40 34","26 32","58 18","87 11","51 65","14 46","73 96","30 49","70 61","3 21","48 81","42 97","82 33","25 21","14 46","40 75","78 68","62 1","37 66","23 3","49 13","37 20","71 53","75 44","46 22","34 0","75 61","26 27","4 64","64 30","80 88","49 4","66 29","54 9","78 4","32 100","50 99","33 84","63 96","52 70"}

    Returns: 0

  7. 40

    {"21 31","51 82","40 78","4 8","58 71","47 71","17 55","66 7","34 31","60 42","32 94","73 55","97 84","52 82","44 1","61 33","46 33"}

    Returns: 28

  8. 3

    {"17 12","85 19","57 25","6 0","29 29","74 59","78 6","32 38","7 47","38 28","93 45","34 83","47 78","26 74","59 5","69 43","74 84","9 28","44 36","69 47","45 78","49 36","30 99","77 98","28 62","70 42","66 63","40 13","77 2","46 23","66 44","21 1","94 66","69 71","7 51","78 34","64 63","54 47","64 69","94 0","95 75","22 83","75 6","3 86","89 70","30 81","49 80","17 89","35 14"}

    Returns: 0

  9. 68

    {"41 97","32 59","10 47","30 46","53 84","14 49","5 77","30 23","52 59","56 96","29 13","22 26","3 45","68 63","63 42","43 74","65 78","48 37","51 7","89 32","83 44","33 45"}

    Returns: 36

  10. 54

    {"90 56","91 79","41 20","15 88","58 92","7 74","44 66","2 35","100 37","71 100","33 72","25 73","33 95","71 40","75 87","44 83","57 62","52 80","60 59","29 64","46 59","9 6","96 85","24 79","76 70","99 16","98 42","15 92","7 61","27 28"}

    Returns: 18

  11. 78

    {"39 73","78 100","2 48","36 80","51 61","83 78","48 41","0 36","49 17","37 30","30 3","78 28","33 15","64 91","29 38","4 61","26 40","37 20","70 76","10 6","100 94","76 14","93 98","42 83","80 38","85 75","12 59","99 50","29 14","62 78","26 1","81 26","14 22","38 10","33 18","59 24","17 49","13 26","3 7","3 66","61 76","98 58","7 20","48 37","35 19","84 88","68 5","56 76"}

    Returns: 0

  12. 51

    {"2 53","29 86","33 6","65 90","37 53","34 32","96 71","55 49","98 67","61 19","83 23","23 81","86 16","60 73","88 67","67 92","100 23","87 50","30 75","51 78","58 40","35 7","2 15","55 14","38 66","0 51","63 63","99 61","65 73","38 65","57 77"}

    Returns: 0

  13. 50

    {"98 100","91 78","85 79","77 28","88 89","5 6","59 57","10 49","21 82","62 74","2 76","5 46","61 90","77 15","100 80","28 80","38 3","61 100","86 0","18 85","93 22","51 32","44 33","91 62","33 2","31 31","52 16","74 86","68 57","14 79","73 43"}

    Returns: 0

  14. 2

    {"44 70","69 85","20 90","21 17","85 87","82 36","14 25","60 20","10 2","18 1","0 66","74 56","87 81","9 13","38 58","81 45","39 33","65 62","41 12","31 55","22 68","22 61","40 42","90 14","30 4","58 70","12 50","12 48","95 68","14 86","76 80","53 65","7 42","44 49","59 40","40 32","49 46","58 4","92 35","86 34","24 48","27 25","75 83","36 85"}

    Returns: 0

  15. 41

    {"88 99","16 14","84 44","65 2","31 13","58 51","64 67","49 58","98 12","30 33","47 80","19 96","97 88","83 39","81 55","66 38","12 46"}

    Returns: 82

  16. 7

    {"27 41","64 45","84 62"}

    Returns: 54

  17. 46

    {"43 61","31 99","66 97","34 7","51 91","0 63","0 52","42 41","22 80","48 43","58 92","97 71","81 70","18 6","36 47","10 78","67 27","38 43","19 75","49 55","52 10","1 68","33 63","1 83","76 2","78 97","54 77","45 43","43 18","61 55"}

    Returns: 0

  18. 52

    {"22 92","24 42","78 93"}

    Returns: 198

  19. 88

    {"60 15","21 59","18 11","76 13","5 69","100 0","46 45","96 45","63 51","19 97","12 26","13 16","47 68","82 18","83 43","38 55","92 4","98 50","50 80","39 67","77 88"}

    Returns: 0

  20. 41

    {"72 62","73 98","70 13","31 1","90 86","28 90","91 87","80 8","96 88","72 57","31 78","75 16"}

    Returns: 41

  21. 63

    {"37 6","19 100","92 57","47 10","22 78","84 70","67 17","29 26","68 75","63 98","62 31","72 31","32 14","79 18","2 72","78 41","87 6","51 60","82 15","2 27","7 69","29 23","47 33","44 76","24 98","77 97","20 23","19 42","51 84","20 46","22 93","91 4","27 34","56 62","91 52"}

    Returns: 22

  22. 9

    {"21 25","77 23","23 88","95 43","96 19","59 36", "80 13","51 24","15 8","25 61","21 22","3 9", "68 68","67 100","83 98","96 57"}

    Returns: 6

  23. 16

    {"3 57","92 40","94 80","96 23","99 57","89 25","74 8","55 30","73 98","18 8","97 82","63 47","69 71","74 25","97 14"}

    Returns: 9

  24. 54

    {"77 81","40 63","34 75","93 26","11 40","51 3","92 80","62 33","100 18","64 56","14 75","5 50","32 87","19 38","21 72","89 44","72 65","19 67","41 65","63 12","33 89","75 65","43 18","29 11","75 23","81 14","81 45","53 83","62 19","22 87","51 70","71 89","100 74","33 39","46 76"}

    Returns: 45

  25. 79

    {"36 36","45 76","57 79","16 61","97 87","10 82","37 55","73 12","86 71","78 1","57 46","71 37","77 59","61 22","94 91","20 4","76 76","30 50","36 77","45 93","17 22","3 36","10 5","13 6","52 66","30 64","51 3","35 94","7 90","0 98","64 39","6 92","54 18","2 80","66 21","10 80","97 66","22 99","100 84","5 12","64 69","67 88","52 91","69 39","94 98","36 17","28 11","58 71"}

    Returns: 0

  26. 14

    {"89 82","48 52","22 23","65 91","75 9","90 42","81 52","33 29","27 38","84 8","33 66","76 58","36 40","22 98","81 80","57 36","49 80","58 16","77 41","35 45","67 40","95 1","21 46","64 49","40 70","94 49","76 23","91 82","69 7","53 58","76 59","87 65","74 99","30 65","41 87"}

    Returns: 14

  27. 18

    {"91 25","20 81","30 62","49 76","89 89","3 51"}

    Returns: 9

  28. 88

    {"60 45","48 34","21 6"}

    Returns: 315

  29. 73

    {"74 87","13 98","63 72","71 93","70 97","24 15","53 47","30 88","11 23","0 41","74 87","79 47","99 39","2 31","78 32","94 29","52 5","22 14","55 83","55 33","77 44","71 68","74 95","89 29","51 11","56 30","5 68","81 63","56 43","70 49","97 37","35 62","35 1","41 50","63 84","78 21"}

    Returns: 0

  30. 42

    {"8 46","0 48","57 34","28 38","28 50","55 81","79 93","74 22","17 51","78 99","77 98","56 64","93 62","81 3","13 23","14 19","77 58","51 89","53 38","68 72","47 54","84 49","63 88","73 58","82 2","79 67","18 75","39 42","11 95","56 30","36 99","41 70","80 8","30 9","51 41"}

    Returns: 0

  31. 92

    {"87 42","31 11","6 10","67 93","44 96","59 72","41 78","92 35","89 29","16 56","71 70","35 25","22 89","49 91","6 2","71 13","78 72","4 36","72 65","94 6","21 95","64 71","89 98","19 89","53 63","29 58","48 13","79 66","63 77","62 6","3 67","6 99","45 1","2 52"}

    Returns: 32

  32. 37

    {"85 15","83 0","22 8","79 17","71 30","67 5","88 83","5 77","44 1","97 73","31 48","29 8","37 4","72 52","63 9","48 56","42 99","1 53","77 10","38 24","5 26","57 9","16 77","97 19","44 67","61 59","15 78","66 10"}

    Returns: 0

  33. 84

    {"87 37","14 80","34 69","5 5","56 18","61 90","32 5","52 39","91 85","100 69","60 8","26 11","87 14","24 61","68 28","81 12","23 41","20 13","58 8","45 84","90 45","3 40","41 95","10 1","87 94","47 33","81 35","54 80","10 42","66 7","2 47","97 65","52 43","19 4","55 59","42 90","91 33","30 12"}

    Returns: 28

  34. 9

    {"21 25", "77 23", "23 88", "95 43", "96 19", "59 36", "80 13", "51 24", "15 8", "25 61", "21 22", "3 9", "68 68", "67 100", "83 98", "96 57" }

    Returns: 6

  35. 13

    {"20 1" }

    Returns: 13

  36. 6

    {"10 0" }

    Returns: 0

  37. 18

    {"1000 1" }

    Returns: 18

  38. 11

    {"22 1" }

    Returns: 11

  39. 1

    {"1 1" }

    Returns: 1

  40. 100

    {"20 1", "30 1", "40 2" }

    Returns: 100

  41. 7

    {"100 2", "111 1" }

    Returns: 7

  42. 100

    {"1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 999", "1000 988", "1000 988", "1000 988", "1000 988", "1000 988", "1000 988", "1000 988", "1000 988", "1000 988", "1000 988", "1000 555", "1000 555", "1000 555", "1000 555", "1000 444", "1000 555", "1000 555", "1000 555", "1000 555", "1000 555", "155 44", "155 44", "155 44", "155 44", "155 44", "155 44", "155 44", "155 44", "155 44" }

    Returns: 2635

  43. 8

    {"1 5", "10 5" }

    Returns: 2

  44. 7

    {"1000 1000", "1 1" }

    Returns: 2

  45. 11

    {"3 4" }

    Returns: 6

  46. 6

    {"22 1" }

    Returns: 6

  47. 7

    {"10 3", "12 2" }

    Returns: 12

  48. 6

    {"10 1" }

    Returns: 6

  49. 7

    {"100 1" }

    Returns: 7

  50. 7

    {"12 1" }

    Returns: 7

  51. 17

    {"12 3" }

    Returns: 36

  52. 100

    {"15 2" }

    Returns: 200

  53. 99

    {"999 1", "999 5" }

    Returns: 99

  54. 100

    {"1000 1000" }

    Returns: 17000

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: