| Codeforces Round 1134 (Div. 4) |
|---|
| Finished |
There are $$$n$$$ piles of stones in a row, numbered from $$$1$$$ to $$$n$$$ from left to right. The $$$i$$$-th pile contains $$$a_i$$$ stones. You are also given an integer $$$k$$$.
Alice and Bob play a game. They take turns, and Alice moves first. In one move, a player chooses a non-empty pile $$$i$$$ and removes one stone from it. Then one new stone is added to each pile $$$j$$$ such that $$$\max(1, i-k) \le j \le i-1$$$, that is, to each of the $$$\min(k, i-1)$$$ piles immediately to the left of pile $$$i$$$. If $$$i = 1$$$, no stones are added. The supply of new stones is unlimited. For example, if $$$i = 5$$$ and $$$k = 2$$$, one stone is added to each of piles $$$3$$$ and $$$4$$$.
The player who cannot make a move loses. It can be shown that the game always ends after a finite number of moves.
Determine the winner if both players play optimally.
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.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2\cdot 10^5$$$, $$$1 \le k \le n-1$$$) — the number of piles and the parameter of the game.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the numbers of stones in the piles.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, print Alice if Alice wins, and Bob otherwise.
52 11 13 20 0 14 10 0 1 05 21 2 3 4 53 12 5 2
AliceBobAliceAliceBob
In the first test case, $$$k = 1$$$ and each of the two piles contains one stone.
In both cases, Alice wins.
In the second test case, $$$k = 2$$$, and Alice has to take the stone from the third pile. Then one stone is added to each of the first two piles, so the piles contain $$$1$$$, $$$1$$$, and $$$0$$$ stones.
In both cases, Bob wins.
| Name |
|---|


