結果

問題 No.3112 Decrement or Mod Game
ユーザー moti
提出日時 2025-04-20 04:10:40
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 934 bytes
コンパイル時間 2,632 ms
コンパイル使用メモリ 139,648 KB
実行使用メモリ 786,324 KB
最終ジャッジ日時 2025-04-20 04:10:57
合計ジャッジ時間 14,092 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1 MLE * 2
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[10010][10010][2];

int dfs(int a, int b, bool is_alice) {
  //cout << a << " " << b << endl;
  if (a < 0 || b < 0) throw "a or b is negative";
  assert(a >= 0 && b >= 0);
  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 > 10000 || b > 10000) {
    throw "a or b is too large";
  }
  rep(i, 10010) rep(j, 10010) rep(k, 2) memo[i][j][k] = -1;
  dfs(a, b, true);  
  cout << (memo[a][b][true] > 0 ? "Alice" : "Bob") << endl;
}
0