Statistics

Problem Statement for "Bookstore"

Problem Statement

Every quarter, the Stanford Bookstore has special deals in which two or more books can be bought together at a reduced price.

As part of their checkout procedure, they need a program that calculates the cheapest price a student can get for the books he is buying.

Write a method cheapest, which, given the individual price of books, and the price of book combinations, returns the cheapest price. You may only place each book in one combination (or no combinations), and each combination may be used at most once.

The input will be a int[] books, which will contain the integer cost of the individual book, in dollars, a int[] checkout, which will contain the number of each book the student is trying to buy (corresponding to the same indexed book in books), and a String[] combos, which will contain the combination deals and prices, formatted as follows:

"[price]:[book],[book],[book]..."

where [price] is an integer representing the combination price in dollars, and each [book] is an integer book number, which is the 0-based index of the book in books. There must be at least 2 books in each combination, but as many are allowed as will fit in the String[] element length constraints.

Definition

Class:
Bookstore
Method:
cheapest
Parameters:
int[], int[], String[]
Returns:
int
Method signature:
int cheapest(int[] books, int[] checkout, String[] combos)
(be sure your method is public)

Notes

  • It is possible for a combination deal to be more expensive than the individual books. In this case, it would not yield the cheapest price and may be ignored.
  • A combination such as "100:0,0" is allowed and means that you can get two books (book 0) for 100. See example 5.

Constraints

  • books will contain between 1 and 50 elements, inclusive
  • checkout will contain the same number of elements as books
  • each element of books will be between 100 and 1000, inclusive
  • each element of checkout will be between 0 and 10, inclusive
  • combos will contain between 0 and 15 elements, inclusive
  • each element of combos will contain between 5 and 50 characters, inclusive, and be formatted as described above, with a single colon (':') after the price, and single commas between book numbers. [price] will be between 50 and 1000, inclusive, at least 2 [book]s, and each [book] will reference an index of books and checkout
  • there will be no leading zeroes for [price] or [book] in the elements of combos
  • each element of combos will contain only digits ('0' - '9'), commas and colons.

Examples

  1. {100,200,300,400,500}

    {1,1,1,0,0}

    {"500:0,1,2","300:1,2","100:0,1,2,3"}

    Returns: 400

    The first combination will take care of all 3 books, for a total price of 500. The second one will take care of 2 of the books for 300, and the third book must be bought at price for a total of 400. The third combination, although seemingly the best, can't be used because none of book 3 is bought.

  2. {100,200,300,400,500}

    {1,1,1,0,0}

    {"50:0,1","50:1,2"}

    Returns: 150

    Either one of the combinations can be used, but both leave a book unbought. The better combination is the second one, since book 0 is cheaper.

  3. {100,200,300,400,500}

    {1,2,1,0,0}

    {"50:0,1","50:1,2"}

    Returns: 100

    This time, both combinations can be used, and they take care of all the books.

  4. {100,200,300,400,500}

    {1,1,1,1,1}

    {"50:0,1,1"}

    Returns: 1500

    Since the combination cannot be used, each book must be bought at price.

  5. {100,200,300,400,500}

    {0,0,0,0,0}

    {"50:0,1,2,3,4"}

    Returns: 0

  6. {100,100,100,100,100,100,100,100,100,100, 100,100,100,100,100,100,100,100,100,100, 100,100,100,100,100,100,100,100,100,100, 100,100,100,100,100,100,100,100,100,100, 100,100,100,100,100,100,100,100,100,100}

    {10,10,10,10,10,10,10,10,10,10, 10,10,10,10,10,10,10,10,10,10, 10,10,10,10,10,10,10,10,10,10, 10,10,10,10,10,10,10,10,10,10, 10,10,10,10,10,10,10,10,10,10}

    {"100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18"}

    Returns: 32000

  7. {396,132,800,115,646,329,258,621,187,955,852, 987,992,610,447,887,978,652,845,603,230,799,404}

    {3,5,7,0,5,4,0,6,3,7,7,0,0,4,9,0,8,5,5,4,0,9,7}

    {"127:15,15,7,9,22,1,1,20", "907:4,21,11,3,11,19,8,16,9,9,14,7,8,0"}

    Returns: 63133

  8. {248,267,609,549,455,310,905,988,133, 631,691,117,835,533,363,908,395,290, 370,923,638,789,816,933,223,686,543, 288,247,949,444,316,885,760,665,269}

    {0,0,3,0,2,1,0,0,4,1,0,4,8,9,8,6,5,6, 0,0,4,1,0,9,1,3,9,5,5,6,1,8,8,4,4,0}

    {"901:16,15,16,13,7,0,12,29,26,35,35,31,34,34", "216:30,16,19,13,24,15,16,33,31,27,13,18,34,14"}

    Returns: 71249

  9. {407,585,274,244,292,344,701,749,429,450,633, 668,276,940,155,991,579,301,980,434,464,883,923}

    {6,6,5,3,6,1,4,3,6,3,9,0,6,2,7,0,1,1,0,6,3,1,4}

    {"697:19,5,14,12,14,0,14,7,17,17,13,13,20,15,20", "914:7,19,22,10,8,17,12", "470:4,2,9,20,14", "773:9,5,20,7,9,17,21,15,18,14,3,11,21", "497:20,8,20,16,21,15,4,22,2,2,17,17,5,12,7,13", "488:21,14,16,14,22,12,7,4,19,5", "697:12,2,20,8,18,7,3,21,5", "185:6,6,13,4,21,16,8,19,9,16,7,21,10,6,5,12,19", "159:6,6,21,8,3,15,12,18,0,4,14,3,3,4,4,2,5,8,8", "299:13,4,11,5,16,19,22,12,18,5,20,13,1,5", "822:16,7,2,18,0,20,5,22,6,2,8,18,9,18,15,19,18", "704:6,17,3,11,22,20,8,6", "808:3,2,2,4"}

    Returns: 30320

  10. {751,602,306,408,331,288,351,106,904,106,921, 142,967,268,327,509,114,819,735,243,246,451, 863,880,735,791,459,467,496,546,309,875,242,122}

    {7,4,8,8,6,3,7,9,3,4,6,5,6,1,1,1,7, 9,7,1,5,1,7,3,3,2,4,1,1,8,8,7,9,0}

    {"617:33,31,7,30,20,26,1,22,21,30,10,5,10,14,27", "355:25,16,6,32,10,11,15,22,3,19,2,24", "465:23,32,22,8,5,18,3,32,21,28,23,0,7,25,22,23", "468:28,24,6,25,20,6,3,12,30,26,15,10,10,24,20", "448:4,1,30,0,22,13,2,2,3,15,7,21,6,3,18,3,6,3", "941:19,5,20,14,26,32", "939:6,31,0,24", "319:31,7,13,18,31,30,29,22,8,33,32,11", "825:9,3,24", "914:29,26,24,1,31,20,11,20,20,11,25,5", "876:28,9,2,14,3,4,1,14,22,17,28", "292:0,21,2,15,31,20,7,17,13,14,21,2,7,15,20,25", "166:32,20,29,1,22,8,28,7,19,33,30,27,8,0,13,18"}

    Returns: 64782

  11. {289,136,960,214,719,946,773,714,981,318,272, 932,902,262,850,140,489,491,882,995,161,516,420}

    {4,0,1,4,9,3,2,9,6,8,7,0,4,3,1,2,8,1,5,1,8,2,4}

    {"835:16,14,15,12,22,4,2,16,7,12,2,1,18,14,18,12", "569:20,6,3,9,0,5,4,21,4,2,3,22,20,22,2,11", "886:14,17,6,5,14,14,16,15,21,21,2,16,4,10,1,9", "104:2,22,5,21,12,3,15,17,4,2,14", "803:18,1,11,7,5,11,0,5,6,6,14,13,17,1", "182:17,1,1,15,7,13,19,14,20,15,8,16,17,18,10,19", "401:22,9,13,20,22,10,0,11,0,1,1,6,21,14,15,20", "788:17,1,17,11,10,4,21,6,10,6,12,1,18,20,15,22", "122:15,19,6,17,15,8,4", "1000:12,17,16,21,7,22,5,21,18,10,6,6,10,18", "858:13,21,10,22,12,15,21,7,16,2,20,18,22,16,0"}

    Returns: 42071

  12. {607,972,443,540,419,715,514,181,979,596, 951,960,723,812,178,372,242,842,462,952,876}

    {7,3,8,2,2,4,2,2,7,0,9,6,7,6,4,7,0,5,1,0,3}

    {"720:13,1", "904:20,17,20,12,10,3,15,17,12,1,19,18,19,3,3", "716:3,6,4,19,5,20", "192:14,1", "649:17,12,15,10,1,16,13"}

    Returns: 56576

  13. {422,262,589,855,620,342,492,974,810,719,893,104, 528,249,912,601,612,799,249,749,279,681,463,772, 164,460,376,859,776,744,424,667,508,639,357,979}

    {8,9,5,3,9,7,1,3,8,6,1,2,3,9,3,7,3,0, 5,9,8,4,1,1,2,2,3,4,7,1,8,2,9,5,6,9}

    {"185:10,20,2,28,8,18,35,34,33", "969:4,6,26,21,19,8,31,1,1,34,19,9,30,6,8,33,13", "212:24,17,34,23,22,24,22,1", "491:2,12,16,24,15,7,7,14,7,2,6,23,27,29,26,16", "194:3,23,31,5,32,25,9", "713:5,28,19,20,2,23,34,11,28,17,17,24,2", "577:23,25,8,26,3,25,20,31,14,31,8,31,4", "204:24,18,20,23,32,24,26,29,1,25,0,12,27", "387:24,33,8,4,34,22,8,19,13,9,7,24,22,28,30,12", "631:21,5", "280:30,8,23", "866:18,3,31,1,0"}

    Returns: 79094

  14. {561,854,981,616,633,285,853,860,718,596, 368,384,901,946,1000,970,293,823,743,905, 530,435,858,911,198,578,390,338,956,718, 212,486,375,565,763,614,800,711,380,359}

    {9,3,7,5,0,0,5,9,4,2,8,9,3,5,4,4,2,4,6,2, 7,7,3,0,5,5,4,7,9,7,8,7,7,5,5,1,2,0,6,0}

    {"710:32,37,14,19", "863:5,19,21,13,9,10,31,0", "893:1,18,24,28,28,29,30,0,28,25,36,29", "680:10,12,33,9,14,39,16,0,11,34,10,16,36,21,20"}

    Returns: 107751

  15. {249,435,694,764,699,325,548,155,171,767, 291,489,931,264,830,203,387,166,941,140, 850,188,283,900,542,791,200,412,792,112, 423,265,624,400,842,730,609,397,587,657, 263,782,435,659,487,462,349,986,290}

    {8,2,4,2,9,8,6,2,7,7,0,5,2,3,2,9, 3,9,3,6,3,5,6,7,2,6,3,0,5,5,2,3, 9,9,3,4,3,3,3,2,5,3,0,7,1,6,5,3,6}

    {"444:16,12,2,9,29,13,45,26,44,35,26,33", "673:2,42,35,22,40,13,15,28,32,11,27", "453:25,38,10,18,6,43,1,38,22,19,7,44,45,43,29", "87:22,21,28,48,15,23,7,30,11,41,20,13,17,13,34", "651:31,30,46,18,10,25,38,25,41,48,13,12,37,11", "465:41,23,41,40,19,5,2,4,48,22,32,8,36,32,34,43", "888:47,15,7,33,1,30,6,25,38,16,25,0,22,5,0,11", "140:4,30,28,32,11,35,42,13,6,13,42,31,29,6,43", "493:35,42,13,31", "611:25,33,6,45,36,3,37,22,12,22,10,37,45,47,30", "949:24,15,28,1,43,5,14,21,0,19,32", "378:26,31,4,28,36,22,33", "838:10,34,1,27,25,15,19,27,33,32,38,10,9,12,12"}

    Returns: 70398

  16. {100}

    {2}

    {"100:0,0"}

    Returns: 100

  17. { 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

    { "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "50:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18" }

    Returns: 310500

  18. { 100, 200, 300, 400, 500 }

    { 3, 3, 3, 3, 3 }

    { "500:0,1,2", "300:1,2", "100:0,1,2,3", "500:0,1,2", "300:1,2", "100:0,1,2,3", "500:0,1,2", "300:1,2", "100:0,1,2,3", "100:0,1,2,3" }

    Returns: 1800

  19. { 500, 500, 500 }

    { 1, 1, 1 }

    { "50:0,1", "50:1,2" }

    Returns: 550

  20. { 100, 100 }

    { 2, 2 }

    { "110:0,1" }

    Returns: 310

  21. { 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000 }

    { 10, 9, 8, 7, 6, 1, 2, 10, 9, 8, 10, 9, 8, 7, 6, 1, 2, 10, 9, 8, 10, 9, 8, 7, 6, 1, 2, 10, 9, 8, 10, 9, 8, 7, 6, 1, 2, 10, 9, 8, 10, 9, 8, 7, 6, 1, 2, 10, 9, 8 }

    { "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18", "100:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18" }

    Returns: 175600

  22. { 100, 100, 100, 100, 100 }

    { 2, 1, 1, 2, 2 }

    { "150:0,1", "150:2,0", "120:1,2", "110:3,4" }

    Returns: 610

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: