2505:A multiplication game

PKU

keyword

C++

概要

n(<2^32)が与えられる。プレイヤーが2人いてゲームを行う。p=1からスタートして、各プレイヤーは交互にpに2~9を掛ける。最初にp>=nとしたプレイヤーの勝ちである。両者が最善を尽くしたとき、先手が勝つか後手が勝つか判定する問題。
いもす先生とはし先生に教えてもらった。
log scaleの数直線を書いて移動できる範囲を書くと、2と9を交互に掛けたところが境界になるらしい。

int main(){
    long long n;
    while(scanf("%lld\n",&n)!=EOF){
        long long x = 1;
        for(int i=0;;i++){
            if(x>=n){
                puts((i&1)?"Stan wins.":"Ollie wins.");
                break;
            }
            x *= (i&1)?2:9;
            fprintf(stderr, "*  %lld\n",x);
        }
    }
    return 0;
}