Bookstore
SRM 122 · 2002-12-04 · by chogyonim
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
"[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
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.
{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.
{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.
{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.
{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.
{100,200,300,400,500}
{0,0,0,0,0}
{"50:0,1,2,3,4"}
Returns: 0
Submissions are judged against all 22 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Bookstore with a public method int cheapest(vector<int> books, vector<int> checkout, vector<string> combos) · 22 test cases · 2 s / 256 MB per case