codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.