|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
A - Dice
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
A simple boardgame that generations of children have played consists of a board containing a trail of squares and a set of colored pieces. At the beginning of the game each player is assigned a piece; all pieces are initially positioned right before the first square of the trail.
The game proceeds in rounds. At each round, players rolls a pair of dice, and move their pieces forward a number of squares equal to the rolled result. Players roll the dice always in the same order (player $A$, then player $B$, etc.) in the rounds.
Most of the squares on the board are plain squares, but some are “traps”. If a player’s piece falls on a trap square at the end of the player’s move, the player misses the next round. That is, she/he does not roll the dice, and her/his piece stays one round without moving. There will be exactly three traps on the trail.
The winner of the game is the player whose piece reaches the end of the trail first. The end of the trail is after the last square of the board. Consider, for example, the board in the figure above, which has squares numbered from $1$ to $48$. At the start, the pieces are positioned at the place marked ‘Begin’ in the figure, that is, before the square number $1$. Therefore, if a player rolls a $7$ (dice showing $2$ and $5$ for example), her/his piece is positioned at square number $7$ at the end of the first round of the game. Furthermore, if a player’s piece is positioned at square $41$, the player needs a roll result of at least 8 to reach the end of the trail and win the game. Notice also that there will be no draw in the game.
You will be given the number of players, the number of squares in the trail, the location of the traps and a list of dice rolls results. You must write a program that determines the winner.
Input
Your program should process several test cases. The first line of a test case contains two integers $P$ and $S$ representing respectively the number of players and the number of squares in the trail ($1 \leq P \leq 10$ and $3 \leq S \leq 10000$). The second line describes the traps, represented by three distinct integers $T_1$, $T_2$ and $T_3$, denoting their positions in the trail $(1 \leq T_1, T_2, T_3 \leq S)$. The third line contains a single integer $N$ indicating the number of dice rolls in the test. Each of the following $N$ lines contain two integers $D_1$ and $D_2$ $(1 \leq D_1, D_2 \leq 6)$, representing the results of the dice rolls. The end of input is indicated by $P = S = 0$. The set of dice roll results in a test will be always the exact number necessary for a player to win the game.
A player is identified by a number from $1$ to $P$. Players play in a round in sequential order from $1$ to $P$.
Output
For each test case in the input, your program should output a single integer: the number representing the winner.
Sample test(s)
Input
2 10
2 4 8
4
1 1
3 4
1 2
6 5
3 7
4 5 7
7
1 2
2 2
2 1
1 1
1 2
1 1
1 1
0 0
Output
1
3