Dice Yutnori
Time limit2sMemory limit512 MB
Given 10 die rolls, move one of four pieces around a branching Yutnori board each turn and maximize the score collected from numbered squares.
- Level
Hard8 of 10
- Topics
- Backtracking, Simulation, Implementation, Brute force
- Solved
- No attempts yet
Problem
Dice Yutnori is played on the following board.
- Initially, four pieces are on the start square.
- A piece may move only in the direction of the arrows drawn on the board. If a piece starts its move from a blue square, it must follow the blue arrow; if it starts its move from a non-blue square, or is in the middle of a move, it must follow the red arrow. When a piece moves to the finish square, its move ends regardless of the number on the die.
- The game consists of 10 turns. On each turn, roll a 5-sided die with the numbers 1 to 5 written one per face, then choose one piece that is not on the finish square and move it by the number on the die.
- If another piece is on the square where a piece would end its move, that piece cannot be chosen. However, if the square where the move ends is the finish square, the piece can be chosen.
- Each time a piece finishes a move, the number written on the square is added to the score.
Given in advance the 10 numbers that will come up on the die, find the maximum score that can be obtained.
Input
The first line gives the 10 numbers that will come up on the die, in order.
Output
Print the maximum score that can be obtained.