Editors note: In future events, a problem at this level of difficulty would only appear in the second half of the competition. I leave it here to maintain the integrity of the original practice event, but do be aware that this would not be used as a day 1 problem in the future.
You have some free time on your voyage across the stars. You start playing the classic childhood game, Snakes and ladders and decide to experiment with recording your moves with your computer.
In our game, each player rolls a regular 6 sided dice, and advances that many positions on the board. If the position they land on is the foot of a ladder, they can climb up the ladder. If the position represents the head of a snake, they have to move downward to the bottom of the snake. The first player to reach the final square wins.
Suppose you have a 6x6 game board. The player starts in the bottom left corner.
0 -10 0 -20 0 0
0 0 0 0 2 0
0 8 0 -9 0 0
0 -3 0 0 0 0
0 0 -6 0 13 0
0 8 0 10 0 0
If they roll a 3, they will advance to the right 3 places and land on the 10 as illustrated.
0 -10 0 -20 0 0
0 0 0 0 2 0
0 8 0 -9 0 0
0 -3 0 0 0 0
0 0 -6 0 13 0
0>>>8>>>0>>10 0 0
As the square was has a value of 10 that represents the foot of a ladder, the player gets to advance forward 10 places as follows. Notice the zig-zag effect with the horizontal direction swapping each time the player climbs a row.
0 -10 0 -20 0 0
0 0 0 0 2 0
0 8 0 -9 0 0
0>>-3 0 0 0 0
0<<<0<<-6<<<0<<13<<<0
0 8 0 10>>>0>>>0
The player has actually landed on yet another special square, which has a value of -3, so they have to go backward 3 places.
0 -10 0 -20 0 0
0 0 0 0 2 0
0 8 0 -9 0 0
0<<-3 0 0 0 0
0>>>0 -6 0 13 0
0 8 0 10 0 0
Finally the player is on a square with a 0, they stop their turn. The next player rolls the dice and has their turn.
The process repeats until one player lands on the top left corner.
The following example represents a 6x6 game board, followed by the dice rolls for two players for 20 rounds.
0 -10 0 -20 0 0
0 0 0 0 2 0
0 8 0 -9 0 0
0 -3 0 0 0 0
0 0 -6 0 13 0
0 8 0 10 0 0
3 6
1 3
4 2
5 3
6 4
3 2
1 4
2 2
4 3
6 4
6 1
1 4
5 2
1 2
5 5
3 1
5 6
5 3
4 1
3 3
In this example game, player 1 wins after 13 moves.
To find the answer, determine which player wins and multiply the player number and by the number of moves required to win. In this example, 1 * 13 = 13, so that is the answer.
Your input data represents a 20x20 grid game board and contains 500 moves for two players.
Find out which player wins, and how many moves it takes them. Multiply the player number and the number of moves required to win together to get your answer value.
A video walkthrough for learning how to solve this problem is available here.