読者です 読者をやめる 読者になる 読者になる

SRM 575 Div2 Medium TheNumberGameDivTwo

問題

SRM 575 - TopCoder Wiki

JohnとBrusがあるゲームをしている,最善の戦略をとった時,勝つ方を答えよと言う問題. ゲームはある数字Xがあった時,Xの1とXではない約数を一つ選び,その数をXから引く,そして相手の手番に移る.もし何も出来ない場合そのターンの人が負ける.

解答

典型的なゲームの問題.

公式の解き方スッキリしている.

class TheNumberGameDivTwo
{
public:
  vector<int> memo;
  bool calc(int n){
    if (memo[n] == 1) return true;
    else if (memo[n] == -1) return false;
    for(int i = 2; i < n; i++) if ((n % i) == 0){
        if(memo[n-i] == -1) return true;
        if (!calc(n-i)){
          memo[n] = 1;
          return true;
        }
      }
    memo[n] = -1;
    return false;
  }
  string find(int n)
    {
      memo = vector<int>(1001, 0);
      memo[1] = -1;
      if (calc(n)) return "John";
      else return "Brus";
    }
};