codeforces-scrape

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

2181F.md (2347B)


      1 Source: https://codeforces.com/problemset/problem/2181/F
      2 
      3 F. Fragmented Nim
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 1024 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 The classical game of Nim goes as follows. There are $n$ piles of stones, and pile $i$ initially consists of $a_i$ stones. Alice and Bob take turns; Alice goes first. On their turn, a player chooses any non-empty pile and removes any positive number of stones from it. The player who takes the last stone wins.
     22 
     23 After playing a lot of Nim, Alice and Bob decided to vary the rules a little bit. In this variation, the player whose turn it is does not choose a pile — their opponent does it for them! However, the player still gets to decide the number of stones to remove from that pile.
     24 
     25 Alice still moves first. On Alice's turn Bob chooses any non-empty pile, and then Alice removes any positive number of stones from it. Similarly, on Bob's turn Alice chooses any non-empty pile, and then Bob removes any positive number of stones from it.
     26 
     27 For the given configuration of stones in the piles, determine who will win if both players follow the optimal strategy.
     28 
     29 Input
     30 
     31 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.
     32 
     33 The first line of each test case contains a single integer $n$, denoting the number of piles ($1 \le n \le 2 \cdot 10^5$).
     34 
     35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, denoting the number of stones in the piles ($1 \le a_i \le 10^9$).
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, print the name of the winner of the game if both players follow the optimal strategy: "Alice" or "Bob".
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 3
     51 
     52 1 2 3
     53 
     54 1
     55 
     56 1
     57 
     58 5
     59 
     60 10 3 4 7 4
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 Bob
     67 
     68 Alice
     69 
     70 Alice
     71 ```
     72 
     73 Note
     74 
     75 In the first test case, here's one possible way the game could proceed:
     76 
     77 * Bob chooses the first pile. Alice removes $1$ stone from it.
     78 * Alice chooses the third pile. Bob removes $2$ stones from it.
     79 * Bob chooses the third pile. Alice removes $1$ stone from it.
     80 * Alice chooses the second pile. Bob removes $2$ stones from it and wins.
     81 
     82 In the second test case, Bob chooses the only pile, and Alice wins by removing the only stone from it.