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

2908 ワード
バックアップアルゴリズム テキストリンク

リンク


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の場合、ウィンドウが勝つほか、上根が勝つ.
    • hdu 1166敵兵布陣(線分樹単点更新)
    線分樹、分散、数学(Variance,玲瓏杯Round#5 H lonlife 1063)