POJ1704ジョージアとボブ（ゲーム）（階段ニム）

Poj1704 Georgia Bob

ジョージアとボブは、自分で発明したゲームをプレイすることにしました。次の図に示すように、紙にグリッドの行を描画し、グリッドに左から右に1、2、3、...の番号を付け、N個のチェスの駒を異なるグリッドに配置します。

ジョージアとボブは順番にチェスの駒を動かします。プレイヤーがチェスの駒を選択するたびに、他のチェスの駒を越えたり、左端を越えたりせずに、チェスの駒を左に移動します。プレイヤーは、チェスマンが移動するステップ数を自由に選択できますが、チェスマンは少なくとも1ステップ移動する必要があり、1つのグリッドには最大で1つのチェスマンを含めることができます。移動できないプレイヤーはゲームに負けます。

ジョージアは「レディファースト」以来常に最初にプレーします。ジョージアとボブの両方がゲームで最善を尽くしていると仮定します。つまり、どちらかがゲームに勝つ方法を知っている場合、彼または彼女はそれを実行することができます。

nのチェスの駒の初期位置を考えると、最終的に誰がゲームに勝つかを予測できますか？
入力入力の最初の行には、単一の整数T（1<= T <= 20), the number of test cases. Then T cases follow. Each test case contains two lines. The first line consists of one integer N (1 <= N <= 1000), indicating the number of chessmen. The second line contains N different integers P1, P2 ... Pn (1 <= Pi <= 10000), which are the initial positions of the n chessmen. Output For each test case, prints a single line, 'Georgia will win', if Georgia will win the game 'Bob will win', if Bob will win the game otherwise 'Not sure'. Sample Input |_+_|Sample Output |_+_|

トピック：

ジョージアとボブは次のゲームをプレイしています。

図に示すように、直線グリッド上にn個のピース​​があります。チェスの駒iは左から円周率の正方形にあります。 GeorigiaとBobは交代で、左に移動するピースを選択します。一度に1つまたは複数のマスを移動できますが、他の駒を追い越したり、同じマスに2つの駒を置いたりすることはできません。

移動操作ができないパーティは失敗します。ジョージアが最初に動くと仮定すると、両方の当事者が最適な戦略を採用したときに誰が勝ちますか？

問題解決のアイデア：

全体としてペアで考えると、このゲームを軽快なゲームに変えることができます。奇数と偶数のピースに従って状況を話し合います。まず、ピース数が偶数の場合を考えてみましょう。ピースを前から後ろにペアで配置すると、ペアになっていないピースをニムの石の山として扱うことができます。石の山の中の石の数は、2つのピースの間の間隔に等しくなります。

この変換が可能な理由を考えてみましょう。ピースのペアの1つを考えると、右のピースを左に移動することは、ニムの石の山から石を取り除くことと同じです。

一方、左のピースを左に動かすと、石の数が増えます。これはニムとは異なります。ただし、相手が石の数を増やしても、石の数を増やしても、追加された部分が元の状態に戻れば、相手が追加された部分を元の状態に戻せば。したがって、ゲームの勝ち負けの状態は、ニムの勝ち負けの状態と一致しています。

ピース数が奇数の場合、左端のピース（つまり、最初のグリッドから左端のピースが最初のペアとして配置されているグリッドまで）に対して特別な処理が実行された後、Nimに変換することもできます。

ACコード：

#include #include using namespace std const int maxn=1000 int n,p[maxn] int main() { int t scanf('%d',&t) while(t--) { scanf('%d',&n) for(int i=0i