結果
| 問題 |
No.3112 Decrement or Mod Game
|
| コンテスト | |
| ユーザー |
 aaaaaaaaaaa
|
| 提出日時 | 2025-04-19 11:13:17 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,067 bytes |
| コンパイル時間 | 1,462 ms |
| コンパイル使用メモリ | 91,400 KB |
| 実行使用メモリ | 814,592 KB |
| 最終ジャッジ日時 | 2025-04-19 11:13:22 |
| 合計ジャッジ時間 | 5,468 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | MLE * 1 -- * 64 |
ソースコード
#include <iostream>
#include <unordered_map>
#include <tuple>
#include <functional> // For std::hash
using namespace std;
// Custom hash for tuple<long long, long long, bool> for unordered_map
struct TupleHash {
size_t operator()(const tuple<long long, long long, bool>& t) const {
auto hash1 = hash<long long>{}(get<0>(t));
auto hash2 = hash<long long>{}(get<1>(t));
auto hash3 = hash<bool>{}(get<2>(t));
// Simple combination of hashes - can be improved for better distribution
size_t seed = 0;
seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= hash3 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
// Using unordered_map for memoization: key is tuple<Alice's number, Bob's number, is_Alice's_turn>
// unordered_map generally provides faster average time complexity for lookups and insertions
// compared to std::map, which can help with runtime performance.
unordered_map<tuple<long long, long long, bool>, bool, TupleHash> memo;
// Function to determine if the current player can win from state (a, b)
// a: Alice's number, b: Bob's number, is_alice_turn: true if Alice's turn, false if Bob's
// Returns: true if current player wins, false otherwise
bool solve(long long a, long long b, bool is_alice_turn) {
// Base case: If either number is 0, the player whose turn it is *now* loses.
// This is because the previous player successfully made their opponent's number zero.
if (a == 0 || b == 0) {
return false;
}
// Check if this state has been computed before using memoization
tuple<long long, long long, bool> current_state = {a, b, is_alice_turn};
if (memo.count(current_state)) {
return memo[current_state];
}
bool can_win = false; // Assume the current player loses initially
if (is_alice_turn) {
// Alice's turn, she has 'a', Bob has 'b'.
// Alice wins if any of her possible moves lead to a state where Bob loses.
// Option 1: Alice subtracts 1 from her number (a). New state: (a-1, b). Bob faces (a-1, b).
// This move is always possible if a > 0, which is true due to the base case.
if (!solve(a - 1, b, false)) {
can_win = true; // Alice wins if Bob loses from (a-1, b)
}
// Option 2: Alice applies modulo on her number (a % b), if a >= b. New state: (a%b, b). Bob faces (a%b, b).
// Only evaluate this move if Alice hasn't already found a winning move (by subtraction).
if (!can_win && a >= b) {
// Immediate win condition by modulo: if a % b == 0 (and b > 0) or b == 1,
// Alice's number becomes 0 (a%b = 0), state becomes (0, b).
// Bob faces (0, b). Since 0 is present, Bob loses (base case). Alice wins.
if (b == 1 || a % b == 0) {
can_win = true; // Immediate win for Alice by modulo
} else { // a%b > 0 and b > 1
// Optimization for a >= 2*b:
// If a is significantly larger than b, the outcome depends on the
// outcome of the game from (a%b, b) and the parity of the quotient a/b.
// This is a specific property derived from the game mechanics.
if (a >= 2 * b) {
// Alice wins if Bob loses from (a%b, b) OR if the quotient (a/b) is even.
can_win = (!solve(a % b, b, false)) || ((a / b) % 2 == 0);
} else { // a >= b && a < 2*b (Ratio is between 1 and 2), a%b != 0, b > 1
// Alice wins if Bob loses from (a%b, b)
if (!solve(a % b, b, false)) {
can_win = true;
}
}
}
}
} else { // Bob's turn, he has 'b', opponent Alice has 'a'. Symmetric logic.
// Bob wins if any of his possible moves lead to a state where Alice loses.
// Option 1: Bob subtracts 1 from his number (b). New state: (a, b-1). Alice faces (a, b-1).
// This move is always possible if b > 0, which is true due to the base case.
if (!solve(a, b - 1, true)) {
can_win = true; // Bob wins if Alice loses from (a, b-1)
}
// Option 2: Bob applies modulo on his number (b % a), if b >= a. New state: (a, b%a). Alice faces (a, b%a).
// Only evaluate this move if Bob hasn't already found a winning move (by subtraction).
if (!can_win && b >= a) {
// Immediate win condition by modulo: if b % a == 0 (and a > 0) or a == 1,
// Bob's number becomes 0 (b%a = 0), state becomes (a, 0).
// Alice faces (a, 0). Since 0 is present, Alice loses (base case). Bob wins.
if (a == 1 || b % a == 0) {
can_win = true; // Immediate win for Bob by modulo
} else { // b%a > 0 and a > 1
// Optimization for b >= 2*a:
// Symmetric property for Bob's turn.
if (b >= 2 * a) {
// Bob wins if Alice loses from (a, b%a) OR if the quotient (b/a) is even.
can_win = (!solve(a, b % a, true)) || ((b / a) % 2 == 0);
} else { // b >= a && b < 2*a (Ratio is between 1 and 2), b%a != 0, a > 1
// Bob wins if Alice loses from (a, b%a)
if (!solve(a, b % a, true)) {
can_win = true;
}
}
}
}
}
// Memoize the result for the current state before returning
memo[current_state] = can_win;
return can_win;
}
int main() {
// Optimize standard I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long A, B;
cin >> A >> B;
// Determine if Alice wins starting from state (A, B) on her turn
if (solve(A, B, true)) {
cout << "Alice" << endl;
} else {
cout << "Bob" << endl;
}
return 0;
}