GameShowTotal
SRM 829 · 2022-05-10 · by misof
Problem Statement
Your friend just took part in a game show.
During the game show your friend was asked a sequence of N questions. The questions were numbered from 0 to N-1 in the order in which they were asked. Each question had an assigned dollar amount: for question i this amount was A[i].
The rules of the game are as follows: The contestant starts the game with an empty bank. Whenever the contestant answers a question correctly, the amount assigned to that question goes to the contestant's bank. But whenever the contestant answers incorrectly, they lose everything that is currently in their bank. At the end of the game the contestant wins the amount that is in the bank at that moment.
You are given the
Your friend claims that in the game show he won exactly W dollars.
You don't know what questions your friend was asked. More importantly, you don't know how he answered and which of his answers were correct.
Return "possible" if your friend can be speaking the truth, or "impossible" if you can be sure that it's not the case.
Notes
- The return value is case-sensitive: the string must be all lowercase.
Constraints
- N will be between 1 and 50, inclusive.
- A will have exactly N elements.
- Each element of A will be between 1 and 1000, inclusive.
- W will be between 0 and 50,000, inclusive.
4
{10, 20, 30, 40}
100
Returns: "possible"
This is clearly possible in exactly one way: your friend must've gotten all four questions right!
4
{10, 20, 30, 40}
0
Returns: "possible"
This is also possible, in multiple ways. Among them, a very natural way is that your friend could've gotten all four questions wrong.
5
{10, 20, 30, 1000, 40}
1000
Returns: "impossible"
Note that the order of questions is fixed. In this particular game it's not possible to win exactly 1000 dollars. Why? Clearly, your friend must have gotten the 1000-dollar question right, but after that question there was one more: the 40-dollar question. If your friend got it right, he would have won at least 1040 dollars, and if he got the last question wrong, he would get nothing at all.
6
{10, 20, 30, 40, 1000, 50}
1050
Returns: "possible"
One valid gameplay: Your friend got question 0 right. In the bank: 10 dollars. Your friend got question 1 wrong. In the bank: 0 dollars. Your friend got question 2 right. In the bank: 30 dollars. Your friend got question 3 wrong. In the bank: 0 dollars. Your friend got question 4 right. In the bank: 1000 dollars. Your friend got question 5 right. In the bank: 1050 dollars.
1
{10}
0
Returns: "possible"
Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GameShowTotal with a public method string verify(int N, vector<int> A, int W) · 73 test cases · 2 s / 256 MB per case