白俊アルゴリズム9658号:石ゲーム4

リンク

https://www.acmicpc.net/problem/9658

質問する

石遊びは二人で遊ぶ面白いゲームです.
机の上にN個の石がある.尚根と昌英は交代で石を取り、石は1つ、3つ、または4つ持つことができる.最後の石を持って行った人はゲームに負ける.
二人が完璧にゲームをするときは、勝者を救うプログラムを書いてください.ゲームは尚根から始まる.

入力

1行目はNです.(1 ≤ N ≤ 1000)

しゅつりょく

尚根がゲームに勝ったらSK、昌英がゲームに勝ったらCYを出力する.

入力と出力の例

プールコード

// 9658번 : 돌 게임 4

#include <stdio.h>

int main(){
  int n;
  scanf("%d",&n);
  if(n % 7 == 1 || n % 7 == 3){
    printf("CY\n");
  }
  else{
    printf("SK\n");
  }
  return 0;
}

解法

上根(SK=0)、ウィンドウ(CY=1)は

に設定.

n=1->昌永勝(1)

n=2->上根昇(0)

n=3->昌永勝(1)

n=4->上根昇(0)

n=5->上根昇(0)

n=6->上根昇(0)

n=7->上根昇(0)

n=8->昌永勝(1)
...
このように繰り返すと、n%7=1またはn%7=3の場合、ウィンドウが勝つほか、上根が勝つ.