Problem J
Peg Game for Two
Jacquez and Alia’s parents take them on many road trips. To
keep themselves occupied, they play a triangular peg game,
meant for one player. In the original game, one player has an
equilateral triangle containing
Ultimately, Jacquez and Alia have gotten bored of playing this game individually. They decide to invent a version that they could play together. In the new version, each peg has a positive point value, and they alternate turns. During a player’s turn, they must make a jump if one is available. The score for a jump is the product of the two pegs involved in the jump.
The total score of a player is the sum of the scores of
their jumps. The game ends when a player has no possible jumps
to make. Each player’s goal is to maximize their own total
score minus their opponent’s total score (at the end of the
game). For example, Jacquez would prefer to win with a score of
For this version of the game, we can display the game state
by replacing each X shown above with
a corresponding value for that peg, and using a value of
Jacquez has had some trouble winning. Write a program to calculate the best he can do, assuming that he starts and both players play optimally.
Input
The input consists of five lines, describing the initial
state of the board. The
Output
Output the value of Jacquez’s score minus Alia’s score at the end of the game, assuming Jacquez starts and both players play optimally.
Sample Input 1 | Sample Output 1 |
---|---|
3 1 6 1 7 8 5 0 3 4 9 3 2 1 9 |
21 |
Sample Input 2 | Sample Output 2 |
---|---|
1 2 3 4 5 6 7 8 9 10 11 12 0 13 14 |
19 |
Sample Input 3 | Sample Output 3 |
---|---|
100 1 17 99 3 4 0 76 33 42 12 13 14 15 16 |
2148 |