Chomp
TCO08 Round 1 · 2008-01-21 · by lars2520
TCO08 Round 1 · 2008-01-21 · by lars2520 · Dynamic Programming
Problem Statement
Problem Statement
The game Chomp starts with a grid 3 cells high and N cells wide.
Two players take turns selecting a remaining cell in the grid, and
chomping (removing) all the cells to the right and above the selected cell
(including the chosen one). The player who chomps the lower-leftmost
cell loses the game. Here is a sample of two moves in the game:
3 XX XX 2 XXXX => chomp(4,1) => XXX => chomp(1,2) => 1 XXXXX XXX XXX 12345 12345 12345Determine which player wins if each player plays optimally, and how many total (for both players combined) turns it takes (the last move is the losing move). The player who will win when playing optimally plays to win as quickly as possible, while the player who is destined to lose plays to make the game last as long as possible. If player 1 will win, return the total number of moves required. Otherwise, return the negation of the number of moves required.
Constraints
- N will be between 1 and 100, inclusive.
Examples
0)
1 Returns: 2
The optimal game is simple: X . . X => . => . X X .
1)
2 Returns: 6
2)
3 Returns: 6
3)
4 Returns: 8
4)
5 Returns: 12
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Chomp with a public method int moves(int N) · 100 test cases · 2 s / 256 MB per case