TopCoder Statistics - 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                    12345

Determine 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.

Definition

Class:: Chomp
Method:: moves
Parameters:: int
Returns:: int
Method signature:: int moves(int N)
(be sure your method is public)

Constraints

N will be between 1 and 100, inclusive.

Examples

1

Returns: 2

The optimal game is simple: X . . X => . => . X X .
2

Returns: 6
3

Returns: 6
4

Returns: 8
5

Returns: 12
6

Returns: 12
7

Returns: 16
8

Returns: 16
9

Returns: 22
10

Returns: 20
11

Returns: 22
12

Returns: 28
13

Returns: 26
14

Returns: 34
15

Returns: 30
16

Returns: 32
17

Returns: 38
18

Returns: 36
19

Returns: 44
20

Returns: 40
21

Returns: 42
22

Returns: 52
23

Returns: 54
24

Returns: 48
25

Returns: 50
26

Returns: 60
27

Returns: 54
28

Returns: 56
29

Returns: 66
30

Returns: 60
31

Returns: 70
32

Returns: 64
33

Returns: 76
34

Returns: 68
35

Returns: 70
36

Returns: 82
37

Returns: 74
38

Returns: 88
39

Returns: 78
40

Returns: 80
41

Returns: 92
42

Returns: 84
43

Returns: 98
44

Returns: 88
45

Returns: 90
46

Returns: 106
47

Returns: 108
48

Returns: 96
49

Returns: 98
50

Returns: 114
51

Returns: 102
52

Returns: 120
53

Returns: 106
54

Returns: 108
55

Returns: 124
56

Returns: 112
57

Returns: 114
58

Returns: 130
59

Returns: 118
60

Returns: 120
61

Returns: 136
62

Returns: 142
63

Returns: 126
64

Returns: 128
65

Returns: 146
66

Returns: 132
67

Returns: 152
68

Returns: 136
69

Returns: 158
70

Returns: 140
71

Returns: 160
72

Returns: 144
73

Returns: 146
74

Returns: 148
75

Returns: 168
76

Returns: 152
77

Returns: 174
78

Returns: 156
79

Returns: 176
80

Returns: 160
81

Returns: 182
82

Returns: 164
83

Returns: 166
84

Returns: 190
85

Returns: 170
86

Returns: 194
87

Returns: 174
88

Returns: 178
89

Returns: 178
90

Returns: 202
91

Returns: 206
92

Returns: 184
93

Returns: 186
94

Returns: 212
95

Returns: 190
96

Returns: 192
97

Returns: 218
98

Returns: 196
99

Returns: 224
100

Returns: 200

Statistics

Problem Statement for "Chomp"

Problem Statement

Definition

Constraints

Examples