codeforces-scrape

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

1965A.md (1783B)


      1 Source: https://codeforces.com/problemset/problem/1965/A
      2 
      3 A. Everything Nim
      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 are playing a game on $n$ piles of stones. On each player's turn, they select a positive integer $k$ that is at most the size of the smallest nonempty pile and remove $k$ stones from each nonempty pile at once. The first player who is unable to make a move (because all piles are empty) loses.
     22 
     23 Given that Alice goes first, who will win the game if both players play optimally?
     24 
     25 Input
     26 
     27 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     28 
     29 The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$) — the number of piles in the game.
     30 
     31 The next line of each test case contains $n$ integers $a_1, a_2, \ldots a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the initial number of stones in the $i$-th pile.
     32 
     33 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     34 
     35 Output
     36 
     37 For each test case, print a single line with the name of the winner, assuming both players play optimally. If Alice wins, print "Alice", otherwise print "Bob" (without quotes).
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 7
     45 
     46 5
     47 
     48 3 3 3 3 3
     49 
     50 2
     51 
     52 1 7
     53 
     54 7
     55 
     56 1 3 9 7 4 2 100
     57 
     58 3
     59 
     60 1 2 3
     61 
     62 6
     63 
     64 2 1 3 4 2 4
     65 
     66 8
     67 
     68 5 7 2 9 6 3 3 2
     69 
     70 1
     71 
     72 1000000000
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 Alice
     79 Bob
     80 Alice
     81 Alice
     82 Bob
     83 Alice
     84 Alice
     85 ```
     86 
     87 Note
     88 
     89 In the first test case, Alice can win by choosing $k=3$ on her first turn, which will empty all of the piles at once.
     90 
     91 In the second test case, Alice must choose $k=1$ on her first turn since there is a pile of size $1$, so Bob can win on the next turn by choosing $k=6$.