# POJ 3537 Crosses and Crosses

Problem Description:
Two players take turn in playing a game on a 1 x N board.
When it is a player's turn, he puts a marker on a grid that had no marker.
If after a movement there are 3 consecutive markers on the board, the player who made that movement wins the game.

Constraints:
1 ≤ N ≤ 2000

Solution:
Obviously, both player will avoid putting marker so that there is "VV_" or "V_V".
Hence a movement is equivalent to splitting the board into two independent games, where two grids left and two grids right will and itself will be eliminated from the game.

Code:

```#include <iostream>
#include <cstring>
#include <vector>

int dp[2000 + 1];

int grundy(int n) {
if (n <= 0) return 0;
if (~dp[n]) return dp[n];
std::vector<int> vis(1 << 11);
for (int i = 1; i <= n; ++i) {
vis[grundy(i - 1 - 2) ^ grundy(n - i - 2)] = 1;
}
for (int i = 0; ; ++i) {
if (!vis[i]) return dp[n] = i;
}
}

signed main() {
std::memset(dp, 0xff, sizeof(dp));
std::ios::sync_with_stdio(false);
int n;
std::cin >> n;
std::cout << (grundy(n) ? 1 : 2) << std::endl;
return 0;
}
```