Connection Status:
Competition Arena > PawnGame

PawnGame

SRM 732 · 2018-03-29 · by ltdtl

SRM 732 · 2018-03-29 · by ltdtl · Search
Class Name: PawnGame
Return Type: int[]
Method Name: WhoWins
Arg Types: (int, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Alice and Maya play the Pawn Game. The Pawn Game is played on a board that consists of r independent rows. The rows are numbered 0 through r-1. Each row is divided into cells. Different rows may have different lengths: row i consists of C[i] cells. The length of each row is at least three. In each row the cells are numbered from 1 to C[i] from the left to the right.


In each row there is exactly one black pawn and exactly one white pawn. Each pawn occupies a different cell: the black pawn in row i starts in the cell b[i] and the white pawn starts in the cell w[i].


Alice controls the black pawns and Maya controls the white pawns. There are two types of valid moves for the black pawns:

  • A black pawn may be moved one cell to the right if that cell exists and is empty.
  • A black pawn may jump over the white pawn (moving two cells to the right) if the next two cells to the right are a cell with a white pawn followed by an empty cell.
The valid moves for the white pawns are the same, the only difference is that the white pawns move and jump to the left.


The two players take alternating turns to play the Pawn Game. Whenever it's Alice's turn, she has to choose one black pawn and make a valid move with it. Whenever it's Maya's turn, she has to move one of the white pawns. If a player is unable to make a valid move, she loses the game.


Consider two different scenarios. In both of them both Alice and Maya play the game optimally. In the first scenario Alice takes the first turn, while in the second scenario Maya is the first one to play. Return a int[] with two elements: the winner of the game in the first scenario, followed by the winner in the second scenario. (The value 1 means Alice wins, the value 2 means Maya wins.)

Constraints

  • r will be between 1 and 50, inclusive.
  • C will contain exactly r elements.
  • Every element of C will be between 3 and 1,000,000, inclusive.
  • b will contain exactly r elements.
  • i-th element of b will be between 1 and C[i], inclusive.
  • w will contain exactly r elements.
  • i-th element of w will be between 1 and C[i], inclusive.
  • For every i between 1 and r, inclusive, b[i] < w[i] will hold.
Examples
0)
1
{4}
{1}
{2}
Returns: {1, 1 }

At the beginning, the only row looks like this: [BW..] where B is the black pawn and W is the white pawn. If Alice starts, her only move is to move B over W, leading to [.WB.]; Maya moves W [W.B.]; Alice then moves [W..B]; Maya cannot move anymore, so Alice wins. If Maya starts, Maya cannot move W because jumping over B would lead it to be out of board. Therefore Alice wins in both cases.

1)
1
{5}
{1}
{5}
Returns: {1, 2 }

The player who starts the game wins in this case.

2)
1
{6}
{2}
{6}
Returns: {2, 2 }
3)
1
{5}
{1}
{4}
Returns: {2, 1 }

At the beginning, , the only row looks like this: [B..W.] where B is the black pawn and W is the white pawn. If Alice starts, her only move is to move B [.B.W.]; then Maya's only move is to move W [.BW..]; Alice moves B over W [..WB.]; Maya moves W [.W.B.]; Alice moves [.W..B]; Maya moves [W...B]; and Maya wins. If Maya starts, her only move is to move W [B.W..]; Alice moves B [.BW..]; Maya moves W over B[WB...]; Alice moves [W.B..]; and Alice wins.

4)
1
{4}
{2}
{4}
Returns: {2, 2 }

Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PawnGame with a public method vector<int> WhoWins(int r, vector<int> C, vector<int> b, vector<int> w) · 69 test cases · 2 s / 256 MB per case

Submitting as anonymous