Clever Geek Handbook

トリミノ

Hi％usename％！

この記事では、コンビナトリアルゲームについて少しお話し、そのうちの1つに対する解決策を理解したいと思います。 人生では、まさにこのタイプのゲームに遭遇します。それらの正式な定義は次のとおりです。
コンビナトリアルゲームは、各プレイヤーがどのように（他のポジションで）プレーできるかを知っているゲームポジションのセットです。
今日は、最も単純なゲームへのアプローチの本質を理解しようとします。この目的のために、以下で構成されるTriminoゲームを検討します。 ） 2人のプレイヤーが順番に、最初のプレイヤーをX、2人目のプレイヤーをYとします。各プレイヤーは、曲を望み通りに空いている席に置きます。 互いに数字を課すことは不可能です。 移動できない人は負けます。 私たちの仕事は、誰が最適なゲームに勝つかを決定することです：XまたはY。

通常のエンディング（歩くことができないもの）のゲームはコンビナトリアルゲームの特性を持っていることがわかりやすいため、Nimゲームに還元することができます。 この種のタスクへの一般的なアプローチは、大きなゲームを多くの典型的な小さなゲームに分割し、それぞれがゲームの合計によってnim値を計算し、すべてのパーティションのmex（最小の排他的）を見つけてゼロと比較することです。 等しい場合はP位置を取得し、そうでない場合はN位置を取得します。 すべては些細なことですが、私たちのゲームでは、少し考えてみると、回避できる小さな困難がいくつかあります。 しかし難しさはこれです：最初のフィールドは長方形の形をしていますが、最初のトリミノを置くと、ゲームを2つに分割します。1つはまったく同じで、もう1つはエッジの1つが曲線である点が異なります。 したがって、私たちのタスク、いくつかのタイプのゲームを作成する方法には他に何も残っていません。そのうちの4つがあります。 概略的には、写真に示されています。



これらの各タイプを個別に検討し、トリミノを任意の位置に配置し、他のゲームの合計に分割します。 次に、どのタイプのゲームに分類できるかを追跡する必要があります。 最初のタイプは、1番と2番の合計に分割されます。数字をどのように回しても、2番は2つの2番目のゲームまたは1番と3番に分けられます。 3番目は2番目と3番目に、4番目は2番目と3番目に分けられます。 対称オプションは同じであり、mexに影響を与えないため、同じであると見なします。そのため、3番目と4番目のオプションはまったく同じであることに気付きます。 以下の図は、分割方法を示しています。



コメントを作成し、トリムタブを慎重に配置して、Java言語で暗記する3つの再帰関数を作成します。

Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  1. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  2. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  3. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  4. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  5. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  6. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  7. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  8. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  10. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  11. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  12. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  13. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  14. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  15. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  16. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  17. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  18. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  19. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  21. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  22. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  23. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  24. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  25. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  26. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  27. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  28. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  29. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  30. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  31. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  32. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  34. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  35. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  36. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  37. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  38. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  39. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  40. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  41. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  42. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }



  43. Copy Source | Copy HTML private static int M = 800 ; private static int [] I = new int [M+ 1 ], II = new int [M+ 1 ],III = new int [M+ 1 ]; static { Arrays.fill(I, - 1 ); Arrays.fill(II, - 1 ); Arrays.fill(III, - 1 ); } private static int I( int n) { if (I[n] >= 0 ) return I[n]; if (n == 0 || n == 1 ) return I[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 1 ; i<n; i++) mex[I(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return I[n] = i; return I[n] = M+1 ; } private static int II( int n) { if (II[n] >= 0 ) return II[n]; if (n == 0 || n == 1 ) return II[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[II(i - 1 ) ^ II(n - i)] = true ; for ( int i= 2 ; i<=n; i++) mex[III(i - 1 ) ^ I(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return II[n] = i; return II[n] = M+1 ; } private static int III( int n) { if (III[n] >= 0 ) return III[n]; if (n == 0 || n == 1 ) return III[n] = 0 ; boolean [] mex = new boolean [M+ 1 ]; for ( int i= 2 ; i<n; i++) mex[III(i - 1 ) ^ II(n - i)] = true ; for ( int i= 0 ; i<=M; i++) if (!mex[i]) return III[n] = i; return III[n] = M+1 ; }







今では答えを出すだけです：

Copy Source | Copy HTML



  1. int n = nextInt（）;
  2. out .println（I（n）== 0 ？ 'Y' ： 'X' ）;




この問題を分析する際に、私は一般的な考え方を示しようとしましたが、それはそのような問題を解決するのとほとんど同じです。 上記のタスクはSPOJアーカイブから取得され、 TRIOMINOリンクで利用できます。



ご清聴ありがとうございました。


More articles:


All Articles