1

コーディング コンテストでパズルを解いていましたが、1 つの質問に行き詰まっています。基本的に、誰かがこの解決策に到達する方法がわかりません。パズルは

アリスとボブは次のゲームをします。彼らは遊ぶ数 N を選びます。ルールは次のとおりです。

  1. Bob が最初にプレイし、2 人のプレイヤーが交互にプレイします。
  2. 自分の番に、プレイヤーは N から N 未満の任意の素数 (1 を含む) を引くことができます。このようにして得られた数が新しい N です。
  3. 手番中に動けなくなった人はゲームに負けます。

両方が最適にプレーすると仮定すると、どちらがゲームに勝つでしょうか?

そして与えられた解は

int main() {
  long int T, N;
  for(scanf("%ld", &T); T > 0; T--) {
    scanf("%ld", &N);
    if (N % 4 == 1) {
      printf("ALICE wins\n");
    } else {
      printf("BOB wins\n");
    }
}
4

1 に答える 1

6

それは一種のNimゲームです。最後に対戦したプレイヤーがN = 1負けます。の場合N % 4 != 1、ボブは次の を作成するために 1、2、または 3 を取ることができ、N ≡ 1 (mod 4)アリスは不利な立場になります。それ以外の場合N ≡ 1 (mod 4)、開始時に、アリスはボブの動きに対抗して、≡ 1 (mod 4)再びボブに番号を残すことができます。

于 2012-11-11T16:07:19.513 に答える