Algoogle

Algorithm for Programming Contest

SRM 619 Div1

Category: TopCoder Tag: math

Easy


問題概要


石が2個以上ある山を1つ選んで, 他の山2つに分ける.
これを2人で交互に繰り返してできなくなった方の負け.
2人が最善をつくすとき先攻の勝敗を出せ.

解法


まず初期状態で不可能な場合は負け.
その他の場合, 毎ターン山は1つ減る.
また1個以上石がある2つの山に1個以上の石が加えられるので, 次の人は山が3つ以上あれば必ず少なくとも2つの山は選択できるはず.
よって負ける場合は山の数が残り2つになった時なので, 初期状態の山の数の偶奇で判断できる.

コード


(619div1easy.cpp) download
1
2
3
4
5
6
7
8
9
10
11
class SplitStoneGame {
public:
    string win = "WIN", lose = "LOSE";
    string winOrLose( vector <int> number ) {
        int cnt = 0, n = number.size();
        rep(i,n) if(number[i] > 1) cnt++;
        if(cnt == 0 or n < 3) return lose;
        if(n%2) return win;
        return lose;
    }
};

Comments