対決問題

// 0 と 1 が勝負をする。
// 0 が先手で n から 1,2,3 のいずれかを引く
// 自分の番で 0 になった場合負けである。
// n == 0 であれば先手の 0 が引けないので 1 の勝ち。
// n == 1 であれば先手の 0 が 1 引けば勝てる。

// 最初にすべてに -1 を入れておく。
int memo[1000001][2];

int f(int n,int c){
  if(n <= 0){
    return 1-c;
  }
  
  if(memo[n][c] != -1){
    return memo[n][c];
  }
  
  // 0
  if(c == 0){
    int ret = 1;
    ret &= f(n-1, 1-c);
    ret &= f(n-2, 1-c);
    ret &= f(n-3, 1-c);
    return memo[n][c] = ret;
  }
  // 1
  else{
    int ret = 0;
    ret |= f(n-1, 1-c);
    ret |= f(n-2, 1-c);
    ret |= f(n-3, 1-c);
    return memo[n][c] = ret;
  }
}