WallGameDiv1
SRM 580 · 2012-12-13 · by ivan_metelsky
Problem Statement
The game is played in turns. In each turn, Rabbit moves first and Eel moves second. In the first turn, Rabbit places the token onto one of the cells in the topmost row, and he pays the associated cost. In each of the following turns, Rabbit moves the token one cell left, right, or down, and pays the cost written in the target cell. (Note that Rabbit is not allowed to move the token upwards.) Eel never moves the token. Instead, in each turn, Eel gets to place some walls. In each turn, Eel may place as many walls as he wants, including none. Each wall must be placed between two adjacent cells in the same column.
The game ends when Rabbit first moves the token into the bottommost row. The game must always be allowed to end. That is, Eel must never place a wall that would prevent Rabbit from reaching the bottommost row from the token's current location. Rabbit's goal is to minimize and Eel's goal is to maximize the total cost paid by Rabbit during the game.
You are given the
Constraints
- costs will contain between 2 and 50 elements, inclusive.
- Each element of costs will contain between 1 and 50 characters, inclusive.
- Each element of costs will contain the same number of characters.
- Each character of each element of costs will be between '0' and '9', inclusive.
{"12"
,"34"}
Returns: 6
One possible gameplay is as follows: Rabbit puts a token on '2' and pays 2. Eel puts a wall between '2' and '4' Rabbit moves the token to '1' and pays 1. Eel does nothing. Rabbit moves the token to '3', pays 3, and the game ends. The total cost is 2+1+3 = 6.
{"99999"
,"99999"
,"99999"}
Returns: 99
Let's label the cells in the following way: ABCDE FGHIJ KLMNO We will not show you the optimal strategy. Instead, we will just show you one possible gameplay. Rabbit puts a token on C and pays 9. Eel puts eight walls: between AF, BG, CH, DI, GL, HM, IN, and JO. Rabbit moves the token to D and pays 9. Eel does nothing. Rabbit moves the token to E and pays 9. Eel does nothing. During next several turns, Rabbit will move the token along the path E->J->I->H->G->F and Eel does nothing. Rabbit moves the token to K, pays 9, and ends the game with total cost 81. In the above example, neither player played optimally.
{"01",
"02"}
Returns: 3
You have to visit both 1 and 2.
{"101",
"030"}
Returns: 3
You need to start at a middle cell.
{"1011",
"4651"}
Returns: 6
Start at cell 1. If you're allowed to go down, do it (cost 6). Otherwise go right (cost 1). If you're allowed to go down, do it (cost 6). Otherwise go left twice (cost 2). If you're allowed to go down, do it (cost 6). Otherwise go right three times and go down (cost 5).
{"1100010",
"3330031",
"0233310",
"3100031",
"2000331",
"3003123",
"0330010",
"0111103",
"0303011",
"0130311"}
Returns: 90
You need 3 turns (left-right or right-left changes) in the same row (no idea which one and which turns) to solve this test case.
{"1201011",
"1732354",
"7547173",
"5405948",
"8138856",
"7044072",
"1246832",
"5432155"}
Returns: 208
You need 4 turns here (again, not sure which row and which turns).
{"11111"
,"90005"}
Returns: 10
Let's label the cells in the following way: ABCDE FGHIJ Again, we will not show you the optimal strategy. Instead, we will just show you one possible gameplay. Rabbit puts a token on C. Eel puts three walls: between BG, CH, and DI. Rabbit moves the token to D and pays 1. Eel puts a wall between EJ. Now Rabbit is forced to move the token back. Rabbit will move the token along the path D->C->B->A->F and Eel does nothing. The game ends with total cost 14.
Submissions are judged against all 72 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WallGameDiv1 with a public method int play(vector<string> costs) · 72 test cases · 2 s / 256 MB per case