2196A.md (2027B)
1 Source: https://codeforces.com/problemset/problem/2196/A 2 3 A. Game with a Fraction 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Alice and Bob have two integers $p$ and $q$, and they are playing a game with these numbers. The players take turns, with Alice going first. On their turn, a player can do one of two actions: 22 23 * decrease $p$ by one (this action is possible if $p \gt 0$); 24 * decrease $q$ by one (this action is possible if $q \gt 1$). 25 26 The game ends when $p = 0$ and $q = 1$. 27 28 Bob wins if at any point during the game the fraction $\frac{p}{q}$ is equal to in value the fraction $\frac{2}{3}$. Otherwise, Alice wins. 29 30 Given the initial values of $p$ and $q$, determine the winner of the game if both players play optimally. 31 32 Input 33 34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 35 36 Each input case consists of a single line containing two integers $p$ and $q$ ($1 \le p, q \le 10^{18}$). 37 38 Output 39 40 For each input case, output: 41 42 * "Alice" if Alice wins; 43 * "Bob" if Bob wins. 44 45 Example 46 47 Input 48 49 ``` 50 6 51 52 4 6 53 54 10 14 55 56 15 15 57 58 7 12 59 60 7000000000000000 10487275715782582 61 62 1000000000000000000 1000000000000000000 63 ``` 64 65 Output 66 67 ``` 68 Bob 69 70 Bob 71 72 Alice 73 74 Alice 75 76 Bob 77 78 Alice 79 ``` 80 81 Note 82 83 In the first input case, the fraction is already equal to $\frac{2}{3}$ by value, so Bob wins. 84 85 In the second input case, one possible sequence of the game is as follows: 86 87 * initially $p = 10, q = 14$; 88 * after Alice's turn $p = 9, q = 14$; 89 * after Bob's turn $p = 9, q = 13$; 90 * after Alice's turn $p = 9, q = 12$; 91 * after Bob's turn $p = 8, q = 12$. 92 93 Bob wins, as $\frac{8}{12}$ is equal to $\frac{2}{3}$. It can be shown that in this example, with optimal play from both players, Bob always wins. 94 95 For the third input case, Alice's optimal strategy will be to decrease $q$ as long as possible. In this case, the game will end in favor of Alice regardless of Bob's actions.