SRM574 Div1 Easy

250

とりあえずメモ化する。意外と間に合う。

const int T = 101;
map< pair<string, string>, int > memo[T];

const int win = 1;
const int lose = 0;

int rec(string a, string b, int turn)
{
  if (a.empty()) a = "0";
  if (b.empty()) b = "0";
  if (turn == 100) return lose;
  if (turn == 101) return win;
  if (a == b) {
    if (turn % 2) return lose;
    else return win;
  }

  pair<string, string> key = make_pair(a, b);
  if (memo[turn].count(key)) return memo[turn][key];

  int best = lose;

  string A = "";
  A = a;
  A.erase(A.begin() + A.size() - 1);
  best = max(best, rec(b, A, turn + 1) ^ 1);
  A = a;
  reverse(A.begin(), A.end());
  best = max(best, rec(b, A, turn + 1) ^ 1);

  return memo[turn][key] = best;
}

class TheNumberGame {
public:
  string determineOutcome(int A, int B)
  {
    char buff1[10];
    char buff2[10];
    sprintf(buff1, "%d", A);
    sprintf(buff2, "%d", B);
    fill(memo, memo + T, map< pair<string, string>, int >());
    return (rec(string(buff1), string(buff2), 0) == win) ? "Manao wins" : "Manao loses";
  }
};