Notice that the order of placing the pieces nor who is the owner of each piece doesn't matter at all. Thus I can make a simple variation of the game: each player has to place a piece in such a way that no more pieces can be added to the left of the piece. Now, the DP is much much simpler.
I also made a more complicated solution that doesn't use the observations described above. It's pure DP implementing the game as it is.
I have tested both approaches and they give exactly the same output for all test cases ( 1 <= n <= 800 ).
This is the code:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
using namespace std;
#define fore( i, x ) for( __typeof( (x).begin() ) i = (x).begin(); i != (x).end(); ++i )
int win[ 802 ][ 2 ][ 2 ];
int lose[ 802 ][ 2 ][ 2 ];
int solvewin( int xn, int xlo, int xhi, int yn, int ylo, int yhi ) {
if( win[xn][xlo][xhi] && !win[yn][ylo][yhi] ) return 0;
if( !win[xn][xlo][xhi] && win[yn][ylo][yhi] ) return 0;
if( lose[xn][xlo][xhi] && win[yn][ylo][yhi] ) return 0;
if( win[xn][xlo][xhi] && lose[yn][ylo][yhi] ) return 0;
return 1;
}
int solvelose( int xn, int xlo, int xhi, int yn, int ylo, int yhi ) {
if( win[xn][xlo][xhi] && !lose[yn][ylo][yhi] ) return 0;
if( !lose[xn][xlo][xhi] && win[yn][ylo][yhi] ) return 0;
if( lose[xn][xlo][xhi] && !lose[yn][ylo][yhi] ) return 0;
if( !lose[xn][xlo][xhi] && lose[yn][ylo][yhi] ) return 0;
return 1;
}
void run() {
int n; scanf( "%d", &n );
if( win[n][0][0] )
printf( "X\n" );
else
printf( "Y\n" );
}
int main() {
for( int lo = 0; lo < 2; ++lo )
for( int hi = 0; hi < 2; ++hi ) {
win[1][lo][hi] = lo | hi;
lose[0][lo][hi] = 1;
lose[1][lo][hi] = ( lo | hi ) ^ 1;
}
for( int n = 2; n <= 800; ++n )
for( int lo = 0; lo < 2; ++lo )
for( int hi = 0; hi < 2; ++hi ) {
win[n][lo][hi] |= 1 ^ win[n-2][1][hi];
if( lo ) win[n][lo][hi] |= 1 ^ win[n-1][0][hi];
win[n][lo][hi] |= 1 ^ win[n-2][lo][1];
if( hi ) win[n][lo][hi] |= 1 ^ win[n-1][lo][0];
for( int i = 1; i < n - 1; ++i ) {
win[n][lo][hi] |= solvewin( i-1, lo, 1, n-1-i, 0, hi );
win[n][lo][hi] |= solvewin( i, lo, 0, n-1-i-1, 1, hi );
}
lose[n][lo][hi] |= 1 ^ lose[n-2][1][hi];
if( lo ) lose[n][lo][hi] |= 1 ^ lose[n-1][0][hi];
lose[n][lo][hi] |= 1 ^ lose[n-2][lo][1];
if( hi ) lose[n][lo][hi] |= 1 ^ lose[n-1][lo][0];
for( int i = 1; i < n - 1; ++i ) {
lose[n][lo][hi] |= solvelose( i-1, lo, 1, n-1-i, 0, hi );
lose[n][lo][hi] |= solvelose( i, lo, 0, n-1-i-1, 1, hi );
}
}
int test; scanf( "%d", &test );
while( test-- ) run();
return 0;
}