You and your friends have gotten together for a Trivia night at the local pub. There are N questions asked during the night. Each question is worth a number of points; the i-th element of the points array 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, and you must answer each question before the next is asked.
In addition, after each correct answer you will receive a token. If you then have tokensNeeded tokens, the pub will immediately take all of your tokens and award you additional bonus points. However, if you get the question wrong, the pub will take away all of your tokens without giving you any bonuses. The bonuses change after each question; element i of the bonuses array 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.
To generate the arrays points and bonuses described above, you should use the following pseudo-code on the arrays p and b, respectively.
Input array: X
Output array: P (size N)
k := 0
M := size of X
For i=0 to N-1
P[i] := X[k]
s := (k+1)%M
X[k] := ( ( X[k] ^ X[s] ) + 13 ) % G
k := s
In the above code, use the value 1001 for G when generating points, and 10001 when generating bonus; this guarantees that all questions will be worth between 0 and 1000 points, inclusive, and that all bonuses will be worth between 0 and 10,000 points, inclusive. In the above code, % represents the modulo operator, and ^ is the binary XOR operator (see the Notes section for the implementation in your language).
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.
|