TopcoderArchiveVisit Topcoder
Archive
SRM4 Dec 2002
SRM 122

Booksale

Problem statement, definition, constraints, and public examples.

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

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.

Back to all problems