MinMaxGame
SRM 800 · 2021-02-08 · by laoriu
Problem Statement
Nam and Quang are playing a game with a sequence of integers A. In the game they take alternating turns. Nam plays first.
In Nam's turn he has to choose two consecutive elements of A. Once he does so, he has to erase the larger of these two elements. (If they are equal, he erases one of them, it does not matter which one.)
Quang's turn also begins with him choosing two consecutive elements of A. However, Quang always erases the smaller of those two elements.
The game terminates when only one element of A remains. Its value V is the result of the game. Nam's objective is to maximize V, while Quang's objective is to minimize V.
Assume that both players play optimally. Determine and return the value of V.
Notes
- Whenever an element gets erased from A, its neighbors become adjacent to each other.
Constraints
- A will have between 2 and 100 elements, inclusive.
- Each element of A will be between 1 and 100, inclusive.
{3, 2, 1}
Returns: 3
There are 2 possible scenarios: - Scenerio 1: In the first turn, Nam chooses the first two elements of A, then erases the larger one. The sequence A now becomes {2, 1}. In the second turn, Quang erases the smaller one amongst the two elements remaining in A. The sequence A now becomes {2}. The game terminates, V = 2. - Scenerio 2: In the first turn, Nam chooses the last two elements of A, then erases the larger one. The sequence A now becomes {3, 1}. In the second turn, Quang erases the smaller one amongst the two elements remaining in A. The sequence A now becomes {3}. The game terminates, V = 3. Because Nam's objective is to maximize V, he will choose scenerio 2.
{6, 6, 6, 6, 6, 6}
Returns: 6
No matter how they play, the last number remaining will always be 6.
{2, 5, 3, 7}
Returns: 2
{4, 5, 1, 6, 5}
Returns: 5
{2, 1}
Returns: 1
Submissions are judged against all 211 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MinMaxGame with a public method int lastNumber(vector<int> A) · 211 test cases · 2 s / 256 MB per case