結果

問題 No.3112 Decrement or Mod Game
ユーザー moti
提出日時 2025-04-20 04:12:42
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 815 bytes
コンパイル時間 1,015 ms
コンパイル使用メモリ 139,264 KB
実行使用メモリ 35,036 KB
最終ジャッジ日時 2025-04-20 04:12:53
合計ジャッジ時間 10,272 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 1
other RE * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cassert>

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); i++)

// Brute force
int memo[2010][2010][2];

int dfs(int a, int b, bool is_alice) {
  if (a - 1 == 0) return is_alice;
  if (a % b == 0) return is_alice;
  if (memo[a][b][is_alice] != -1) return memo[a][b][is_alice];
  if (a >= b) {
    memo[a][b][is_alice] = dfs(b, a % b, !is_alice);
  }
  return memo[a][b][is_alice] = max(memo[a][b][is_alice], (int)dfs(b, a - 1, !is_alice));
}

int main() {
  int a, b; cin >> a >> b;
  if (a > 2000 || b > 2000) {
    throw "a or b is too large";
  }
  rep(i, 2010) rep(j, 2010) rep(k, 2) memo[i][j][k] = -1;
  dfs(a, b, true);  
  cout << (memo[a][b][true] > 0 ? "Alice" : "Bob") << endl;
}
0