Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1957-383f3cab
この記事にトラックバックする(FC2ブログユーザー)

April 2011 Challenge 5問目 - Number Game Revisited (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 5問目
Problem Statement
April 2011 Challengeの参加記録

問題概要

2人でゲームを行う.順番に行動し,打つ手がなくなったら負け.先手必勝か後手必勝か判定する問題.
最初正整数N (10^9以下) が書かれている.
1または2以上N未満の素数を選び,Nから引く.(N=1のときは1も選べず負けになる)

解法

取り敢えず小さい範囲で全探索してみると,n mod 4 = 1の時のみ後手必勝になることがわかる.
何故かというと,結果が分かってしまえば,例えば必勝法としては,
 2には2で返す
 4n+1には3で返す
 4n+3には1で返す
ことで,mod 4で不変にできることに気づく.(4nは素数じゃないから打てない)

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n;
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d",&n);
    if(n%4==1) puts("ALICE"); else puts("BOB");
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1957-383f3cab
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。