Statistics

Problem Statement for "Booksale"

Problem Statement

Every quarter, the Stanford Bookstore throws a booksale where there are special deals in which two or more books can be bought together at a reduced price.

Given the price of individual books and the price of combination deals, return the amount of money that the best deal saves for students.

The input will be a int[] books, which will contain the integer cost of the individual book, in dollars, and a String[] combos, which will contain the combination deals and prices, formatted as follows:

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

where the [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 a combination, but as many are allowed as will fit in the String[] element length constraints.

If no combinations exist, or none will save any money, return 0.

Definition

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

Notes

  • It is possible for a combination deal to be more expensive than the individual books. If this is the case for all combinations, return 0.
  • A combination such as "100:0,0" is allowed and means that you can get two books (book 0) for 100. See example 3.

Constraints

  • books will contain between 1 and 50 elements, inclusive
  • each element of books will be between 100 and 1000, inclusive
  • combos will contain between 1 and 50 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 two [book]s, and each [book] will reference an index of books
  • 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}

    {"200:0,1"}

    Returns: 100

    There is only one combination.

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

    {"200:1,2","200:2,3","200:3,4"}

    Returns: 700

    The best combination is the last one.

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

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

    Returns: 0

    None of the combinations saves any money.

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

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

    Returns: 200

    All of the combinations save 200.

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

    {"450:1,3,1,0","800:2,3,2","630:4,4,0","98:1,3"}

    Returns: 202

    The first combination saves 150, the second saves 200, the third saves 170, and the last one saves 202.

  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}

    {"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: 1800

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

    {"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: 7956

  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}

    {"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: 7077

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

    {"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: 10117

  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}

    {"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: 9315

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

    {"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: 10362

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

    {"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: 10259

  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}

    {"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: 10281

  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}

    {"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: 7536

  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}

    {"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: 8222

  16. {852,795,357,489,388,137,436,555,259,772, 904,651,894,313,261,348,740,800,240,149, 241,569,559,554,123,618,849,201,800,105, 965,597,938,384,942,801,698,883,689,531,131}

    {"999:5,24,40,6,17,26,2,14,8,24,12,29,5,21", "265:38,24,34,26,14,2,21,35,22,25,30,21,28,10,12", "339:5,39,28,12,9,16,12,36,13,3,17,26,16,32,5,37", "828:5,32,17,26,26,7,25,20,8,17,15,11,31,25,23", "911:9,15,26,11,19,19,29,20,15,32,13,25,28,37,39", "650:9,1,14,31,3,12,19,17,3,10,24,38,12,8,18", "334:22,21", "179:37,4,7,22,14,20,37", "569:37,30,4,28,37,15,3,25,27,36,37,36,20,30,11", "865:24,14,12,21,3", "456:35,23,9,24,24,17,27,26", "146:26,40,25", "281:24,1,2", "467:8,39,6,32,39,31,26,19,31,2,25,31,9,16,9,34", "715:6,36,29,26,38,29,35,21,35,19,10,34,21,10,39", "280:23,40,23", "80:25,4,4", "419:22,11,6,3,34,15,10,33,31", "915:9,6,5,15,10,26", "971:0,37,20,2,37,2,26,38", "471:18,39,31,0,8,14,7,6,13,34,27,40,12,37", "768:32,18,15,23,11,13,17,5,9,27,27,27,1,14,3,12", "142:33,7,30,26,22,0,30,16,11,21,15", "257:1,32,39,22,39,32,27,13,14,35,24,9", "773:37,17,14,14,3,39,16,35,19,5,7,30,30,24,31", "623:6,17,12,39,36,35,39", "405:2,14,20", "768:24,28,16,21,20,15,19,29", "236:27,32,14,21,25,10,27,11,15,0,34,40,23,3,0", "743:27,36,8,0,34,0,21,3,19,9,30,18,40,28,35,19", "568:2,1,29,33,5,33,22,39,6,36,11,25,31,5,27,0", "925:33,7,27,5,38,14,31,36,1,26,36,15,38,1,30,32", "398:40,31,5,39,14,20,18", "244:16,8", "949:24,40,16,27,15,11,29,21,10,15,33,4,39", "909:13,12,25,0,11,36,34,39,32,40,20,2", "753:28,9,1,9,4,39,20,33,11,12,12,1,35,39,13,40", "569:29,20,34,36,3,11,24,9,34,31,10,1,39", "508:25,30,27,40,10,36,30,40,31,20,32,32,21,23", "188:2,38,20,23,34,19,31,10", "713:4,22,15,9,28,16,2,40,39,25,12,39,6,8,40,30", "314:21,24,2,7,32", "330:29,12,14,15,2,30,38", "419:30,15,32,24,9,28,8,32,11,4,13,31,5,12,38,10", "842:17,18,21", "912:13,5,14,8,9,10,28,29,2,22,23,2,32,1,33", "771:18,3,36,21,28,27,20,13,24,17,24,12,38,14,16", "294:8,16,37,39,28,30,7,24,23,19,0,19,12,21", "72:17,34,5,40,26,1,34,40", "680:3,27,28,12,19"}

    Returns: 10276

  17. {577,924,340,744,754,270,792,744,124,363,204, 992,636,296,226,823,731,483,241,124,471,370, 952,375,683,389,421,651,613,773,701,848,874, 610,579,332,611,428,328,678,190,589,245,521}

    {"396:2,33", "339:6,24,35", "693:26,19", "915:17,30,10,32,6,0,5,13,19,18,5,42,27,33,35,21", "156:32,28,24", "199:39,18,24,6,0,12,28,17,29,3,5,27,7,12,0,20", "366:11,39,29,19,1,40,24,26,0,4,39,22,22,38,14", "774:5,34,20,9,11,9,20,25,21,34,1,13,39,27,0,35", "234:37,17", "267:32,30,41,24,27,15,29,17,22,30,41,24,42,10", "433:14,8,43,15,30,6,3,32,17,36,27,18,9,1,28,27", "557:25,23,29", "464:37,37,0,28,11,16", "883:20,14,13,0,37,30,17,10,10,19,32,17,31,10,16", "322:35,39,21,30,4,26,26,24,4,33,40,2,23,19,21", "967:22,17,34,7", "326:25,42,22,32,25,3,32,10,23,35,17,11,36,25,16", "154:25,43,15,8,9,38,13,34,25,40,21,33,7,35,1,43", "942:41,35,26,22,23,25,12,10,31,36,21,33,25,35", "92:39,42,4,11,9,9,23,31,43,16,29,1,9,37,11", "732:3,2,11,16,40,23,24,19,12", "883:39,42,5,15,27,5,37,34,12", "119:41,41,15,11,35,24,9,43,32,32,36,31,13", "780:3,23,11,7,23,20,40,30,6,2,30,14,30,35,1,32", "797:2,40,37,33,36,19,31,8,41,18,4,19,6", "421:40,15,35,19,3,23", "882:4,25,1,42", "358:14,41,23,7,14,24,20,34,17,8,1,30,26,6,41,22", "161:1,13,6,10,10,37,26,43,6,24,20,7,22,30,8,8", "808:36,4,36,7,27,12,5", "774:39,39,24,11,22,38", "564:11,17,0,0,15,4,18,43", "77:30,21,16,27,5,33,8,38,38,37,3,31,10,42,8,25", "349:19,24", "88:26,28", "812:43,13,22,26,2,11,26,16,1,36,5", "827:28,17,37,17,16,9,39,37,12,37", "229:41,9,9,18,10,36,31,43,4,38,35,5,18,2", "957:3,13,35,38,15,23,16,10,4,26,20,36,16,10,40", "730:4,26,30,20,37,4,4,18,35,24,21,22,9,41,20,17", "539:1,39,16,17,38,25,11,21,41,17,42", "844:43,33,23,41,33,13,35,7,39", "604:41,43,29,12,0,40,9,17,29,21,19,35,42,39,13", "914:32,11,18,22,31,40,31,20,38,7,18,41,0,16", "415:23,23,3,21,42,40", "831:28,7,41,37,13,36,3,27,12,42,22,0,14,0,3,30", "644:7,4", "601:42,26,21,40,38,38,14,30,35,2,16,27,36", "383:26,5,9,20,25,8,2,11,8,5"}

    Returns: 9370

  18. {556,786,805,196,507,519,713,819,235,288,956, 800,859,180,955,498,575,637,122,617,417,761, 247,860,191,852,878,747,922,839,567,292,131, 278,263,109,271,126,719,472,857,329,817}

    {"306:8,6,20,34,38,26,42,28,27,30,41,16", "85:15,36,22,18,16,12,3,42,16,35,21,3,16,26,0,15", "394:39,22,25,21,38,15,9,13,33,27,3,4,3,28,22,5", "753:36,39,10", "82:2,37,21,38,20,21,12,1,10,19,13,0,12,28,36,38", "752:0,34,25,25,23,17,30,42,31,35,27,26,42,9,29", "623:14,19,31,21,14,35,28,40,5,34,28", "420:21,8,42,5,34", "752:2,13,25,13,24,21,1,27,19,7,8,5,35", "449:35,2,34,23,22,7,36,42,15,18,39,6,36,11,11", "269:9,17,16,1,2,12,26,12,3,17,37,2,5,4,33,8,24", "656:26,6", "138:30,19,36,3,18,25,7,33,17,8,34,28,17,2", "268:24,17,21,20,5,32,13,38,34,39,26,40,16,41,35", "616:12,36,37,35,35,37,27,29,7,9,8,12,21,42,0,13", "957:32,30,11,20,24,29,15,28", "462:36,5,31,3,40,24,42,3,23,15,24,28,32,14,32", "548:34,38,36,36,27,35,19,40,19,35,22,35,15,13", "542:1,30,3", "938:3,20,39,12,37,30,32,31", "721:4,42,7,17,34,8,34,24,24,19,15,26", "897:41,3,33,13,38,17,15,34", "809:28,1,33,29,3,24,39,39,27,29,6,39,1,19,37,17", "614:3,11,39,22,11,26,9,6,35,38,41", "567:12,10,7,5,15,3,3,39,20,27,28,30,38,30,38,16", "202:18,39,6,16,20,42,33,4,12,37,36,30", "982:34,20,2,3,5,1,26,10,36,25,30,5", "737:24,20,35,6,23,30,11,24,41,6,18,15", "386:14,15,6,30,29,3,29,20,34,41,30,8,21", "997:11,3,8,31,25,23,8,34,19,38,18,15,42,19,40", "443:35,21,23,29,32,33,39,40,39,21,24,27", "747:23,3,29,11,40,26,0,25,20,39,35,29,15,36", "821:35,9", "92:11,15,2,21,36,31,42,13,32,8,31,16,35,9,12,25", "180:11,11,24,11,0,10,27,18,35,21,12,3,1,2,14,41", "675:15,18,11,22,1,27,4,20,12,0,35,19,13,0,31,28", "689:10,38,37", "517:23,10,42,21,28,14,26,36,30,7,7,26,19,28,23", "532:5,25,40,6,4,3,16,22,36,25,10,0,6,17,30,25", "381:19,33,8,4,19,24,36,41,29,28,29,6,27,21,40", "410:7,35,2,15,6,42,10,38,39,20,15,21,17,16,11", "52:19,1,23,15,8,13,12,10,30,25,16,29,30,30,21", "488:33,23,25,13,14,38,4,22,21,6,28,12,5,20,18", "502:8,5,1,5,3", "299:9,10,18,40,36,18,0,22,20,33,13,6,5,13,37,30"}

    Returns: 11385

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

    { "200:0,1" }

    Returns: 100

  20. { 200, 100, 400, 200, 300 }

    { "450:1,3,1,0", "800:2,3,2", "630:4,4,0", "98:1,3" }

    Returns: 202

  21. { 1000, 1000, 1000, 1000, 1000 }

    { "1000:0,1" }

    Returns: 1000

  22. { 100, 200 }

    { "60:0,1", "70:0,1" }

    Returns: 240

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: