アルゴリズム

ゲーム理論ニムゲーム階段ニム階段ニムPOJ1704ジョージアとボブ



Game Theory Nim Game Staircase Nim Staircase Nim Poj 1704 Georgia



  • ニムゲーム

アイテムの山がn個あるとすると、i番目の山にはAiがあります。 2人のプレイヤーが交代で行動を起こします。選択するたびに、山、アイテムをいくつでも取り去り、光の山を取りますが、それを行う必要があります。最後のアイテムをとった方が勝ちです。どちらも最善の戦略を取り、先発者が勝つかどうかを尋ねました。

  • 定理
    NIMゲームは、A1xorA2xor…xorAn≠0の場合にのみ勝ちます。



  • 階段ニム
    一方向に動き、最後に歩けないものが失われます。データの総数nのパリティに従って、パイルが分割され、ニムゲームのAiが決定されます。

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



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

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

プレイヤーの初期位置を考慮して、誰がゲームに勝つかを予測できますか？



サンプル

Sample input 2 3 1 2 3 8 1 5 6 7 9 12 14 17 Sample output Bob will win Georgia will win

nが奇数の場合、奇数を1つのグループにグループ化し、nが偶数の場合、偶数を1つのグループにグループ化します。Aiは、各グループの2つの数値間の距離です。

コード

#include #include using namespace std const int N = 1010 int a[N] int n int main(){ int t cin >> t while(t--){ cin >> n int ans = 0 for(int i = 1 i <= n i++) cin >> a[i] sort(a + 1, a + 1 + n) if(n & 1){ for(int i = 1 i <= n i += 2){ ans ^= a[i] - a[i - 1] - 1 } } else{ for(int i = 2 i <= n i += 2){ ans ^= a[i] - a[i - 1] - 1 } } if(ans == 0) cout << 'Bob will win' << endl else cout << 'Georgia will win' << endl } return 0 }