WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM575 Div2 Medium "TheNumberGameDivTwo"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12497

ジョンとブロスが数字を使ったゲームを行う。
このゲームは正の整数nからスタートする。
ジョンのターンから始まり、2人交互にターンが回ってくる。

各ターンは次のようにする。
ターンが回ってきたときの数字がCだとする。
そのターンのプレイヤーはCの正の約数を1,C以外から選ぶ。
そしてその約数をCから引く。
その結果が次のターンで対戦相手が扱う数字となる。
もし、この動作を行う事が出来なければ、そのプレイヤーの負けとなる。

n=15としてゲームの一連の流れの例を示す。

15でジョンのターン。3を選ぶ。15-3=12
12でブロスのターン。4を選ぶ。12-4=8
8 でジョンのターン。2を選ぶ。8-2 =6
6 でブロスのターン。3を選ぶ。6-3 =3
3 でジョンのターン。約数が1,3しかないのでジョンの負け!

nが与えられる。また、両プレイヤーが最善を尽くすと仮定する。
どちらのプレイヤーが勝つかを返せ。

制約

1 <= n <= 1000


考えた事

自分のターンで素数が回ってきたら負けだな。

まずdpを素数=負けで初期化しとく。
あとはゲームの問題にありがちなdp更新をする。

相手が負けになるような動き方があれば勝ち。
どう動いても相手が勝ちになれば負け。


ソースコード

class TheNumberGameDivTwo {
public:
    string find(int n){
        bool win[1001];
        memset( win, false, sizeof(win) );

        // 素数だけ負け
        for( int i = 2; i <= 1000; i++ ){
            if( win[i] ) continue;
            for( int j = i + i; j <= 1000; j += i ){
                win[j] = true;
            }
        }
        
        
        for( int i = 2; i <= 1000; i++ ){
            if( !win[i] ) continue;
            // どの素因数を引いても勝ちの場合は負け
            bool ok = false;
            for( int j = 2; j < i; j++ ){
                if( i % j ) continue;
                if( !win[i-j] ) ok = true;
            }
            if( !ok ) win[i] = false;
        }

        return win[n] ? "John" : "Brus";
    }
};