Hey! That's My Fish!
Time limit2sMemory limit1024 MB
Two players place penguins on a row of fish cards and take turns moving them, maximizing their fish difference. Find the first player's best result.
- Level
Medium7 of 10
- Topics
- Game theory, Dynamic programming, Bit manipulation
- Solved
- No attempts yet
Statement
One of the popular board games, Hey! That's My Fish!, is about moving penguins and collecting fish on a board. This is a simplified version of that game. The game uses cards with pictures of fish and penguin tokens.
At the start, the cards are laid out in a row on the table in some order.
Each player gets two penguins. First, the first player places one of their penguins on an unoccupied ice floe. Then the second player does the same. After that, they place their second penguins in the same way.
Once all penguins are on ice floes, the fishing begins! Players take turns. A turn consists of moving one of the current player's penguins. After that, the player takes the ice floe on which that penguin stood at the start of the turn and places it in front of themselves.
A penguin can move across ice floes in any direction and stop on any unoccupied ice floe. It is forbidden to jump over other penguins and over the holes left after ice floes are removed. If a penguin has an obstacle on both sides, it cannot move.
If a player cannot move any of their penguins, they take all of their penguins along with the ice floes those penguins stand on. After that, the second player keeps moving as long as they can move their penguins.
When the game ends, each player counts the fish on all the cards they collected. A player's goal is to maximize the difference between their fish count and the opponent's fish count. What is the maximum difference the first player can obtain if the second player plays optimally?
Input
The first line contains the number of cards (). The second line contains integers , the number of fish on each card, in the order the cards are laid out on the table. .
Output
Print one number: the maximum difference the first player can obtain if the second player plays optimally.
Hint
Game play for the test in the statement:
At the start of the game, there are no penguins on the board:
The first player places the first penguin:
The second player places the first penguin:
The first player places their second penguin:
The second player places their second penguin:
The first player's move:
The second player's move:
The first player's move:
