Connection Status:
Competition Arena > Booksale

Booksale

SRM 122 · 2002-12-04 · by chogyonim

SRM 122 · 2002-12-04 · by chogyonim
Class Name: Booksale
Return Type: int
Method Name: best
Arg Types: (vector<int>, vector<string>)
Problem Statement

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.

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
0)
{100,200,300,400,500}
{"200:0,1"}
Returns: 100

There is only one combination.

1)
{100,200,300,400,500}
{"200:1,2","200:2,3","200:3,4"}
Returns: 700

The best combination is the last one.

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

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

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

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

Coding Area

Language: C++17 · define a public class Booksale with a public method int best(vector<int> books, vector<string> combos) · 22 test cases · 2 s / 256 MB per case

Submitting as anonymous