TriviaGame
SRM 395 · 2008-03-26 · by connect4
Problem Statement
You and your friends have gotten together for a Trivia night at the local pub. Each question is worth a number of points; the i-th element of points corresponds to the score received if you correctly answer the i-th question, but you lose that many points if you answer it incorrectly. The questions are given in the order specified in points, and you must answer each question before the next is asked.
In addition, after each correct answer you will receive a token, and you keep all of your tokens if you answer a question incorrectly. If you then have tokensNeeded tokens, the pub will immediately take all of your tokens and award you additional bonus points. The bonuses are different for each question; element i of bonuses corresponds to the bonus you receive if you win the bonus on question i. Note that it is possible to receive multiple bonuses during the game (see example 0).
You know the answer to all the questions and want to maximize the number of points that you receive. Return the maximum points that you can receive if you correctly choose which questions to answer.
Constraints
- points will contain between 1 and 50 elements, inclusive.
- Each element of points will be between 0 and 1000, inclusive.
- tokensNeeded will be between 1 and 50, inclusive.
- bonus will contain the same number of elements as points.
- Each element of bonus will be between 0 and 10000, inclusive.
{1, 2, 3, 4, 5, 6}
3
{4, 4, 4, 4, 4, 4}
Returns: 29
Answering all six questions correctly will yield the best score in this case, obtaining the bonus after answering the 3rd and 6th questions.
{1, 2, 3, 4, 5, 6}
3
{1, 1, 1, 20, 1, 1}
Returns: 39
Here, it is better to get the first question wrong so that you get the big bonus on the 4th question.
{150, 20, 30, 40, 50}
3
{0, 0, 0, 250, 0}
Returns: 500
Here, your optimal strategy is to get the second question wrong. Then, you will have 3 tokens after the 4th question, so that you can cash in on the big bonus.
{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}
1
{10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000}
Returns: 550000
Maximum test case.
{0}
12
{10000}
Returns: 0
Minimal test case
{100, 100,100, 100,100, 100,100, 100,100,
100, 0,100, 0,100, 100,100, 100,100,
100, 100,100, 100,100, 100,100, 100,100,
100, 100,100, 100,100, 100,100, 100,100,
0, 0,0, 0,100, 100,100, 100,100,
100, 100, 100, 100, 100}
10
{0, 0, 0, 0, 0, 0, 0, 0, 10000,
0, 0, 0, 0, 0, 0, 0, 0, 2000,
0, 0, 0, 0, 0, 0, 0, 0, 10000,
0, 0, 0, 0, 0, 0, 0, 0, 4000,
0, 0, 0, 0, 0, 0, 0, 0, 2000,
0, 0, 0, 0, 10000}
Returns: 23400
Trying to trip up greedy solutions that simply try to pick the cheapest n questions to answer wrong.
Submissions are judged against all 67 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TriviaGame with a public method int maximumScore(vector<int> points, int tokensNeeded, vector<int> bonuses) · 67 test cases · 2 s / 256 MB per case