Alice and Bob play the following game : There are N piles of stones with Si stones in…
- User
Alice and Bob play the following game :
There are N piles of stones with Si stones in the ith pile. Piles are numbered from 1 to N. Alice and Bob play alternately, with Alice starting. In a turn, the player chooses any pile i which has atleast i stones in it, and removes exactly i stones from it. The game ends when there is no such pile. The player who plays last wins the game. Assuming Alice and Bob play optimally, who will win the game? Input
The first line contains the number of test cases T ( ≤ 100). There follow 2T lines, 2 per test case. The first line of each test case conains N ( ≤ 100), the number of piles. The second line contains N space seperated integers, specifying the number of stones in pile 1, pile 2, ..., pile N. There will be atleast 1 and atmost 1000 stones in any pile.
Output
Output T lines, one per test case. For each test case, output "ALICE" if Alice wins the game, and "BOB" if Bob wins the game.
Example
Input: 2 1 1 2 1 1
Output: ALICE ALICE
Assistant
We are given a combinatorial impartial game. There are N piles, numbered 1 to N. In a turn, a player can choose any pile i (presumably 1-indexed) such that the pile has at least i stones, and remove exactly i stones from it. The game ends when no pile has at least its index number of stones (i.e., for all i, S_i < i). The player who makes the last move wins.
We need to determine, given initial piles S_i (1 <= i <= N), who wins assuming optimal play. N <= 100, each pile <= 1000.
This is an impartial game, so we can compute Grundy numbers for each pile? But careful: the move depends on the index i, which is fixed per pile. However, piles are independent? Usually in impartial games, the overall game is the disjunctive sum of the subgames, if moves affect only one pile and the move options for a pile depend only on that pile's state and its index. Indeed, each pile is a separate component, because a move selects one pile and modifies only that pile. The game is the sum of N independent impartial games. Then the outcome (winning for the next player) is determined by the XOR of the Grundy numbers of each pile (Sprague-Grundy theorem). So we need to compute Grundy numbers for a single pile with index i and initial stones S.
For a given pile i, the allowed moves: from state x (stones remaining), we can move to state x - i, provided x >= i. That's it. There is no other move, because the move is always to remove i stones from that pile. However, is there also the possibility of choosing the same pile multiple times? Yes, as long as after each removal, the pile still has at least i stones, we can remove another i. But after some removals, the pile may become less than i, then no more moves from that pile.
So the pile game is essentially: Starting with S stones, a move reduces the stones by i, provided the current stones >= i. The game ends when stones < i. So it's like a subtraction game with subtraction size i. But note: The state after a move is S - i, but can we later remove i again if S - i >= i? Yes. So the game is just the subtraction game where you can subtract i any number of times as long as the pile size remains >= i. This is equivalent to taking the pile modulo i? Actually, the game ends when the pile size is in [0, i-1]. But note: If the pile size becomes exactly 0, that's allowed (since 0 < i, no moves). The player who makes the last move (i.e., reduces the pile from a state >= i to a state < i) wins. So this is a simple impartial game: from a pile of size x, the moves are to x - i if x >= i. The terminal positions are x < i.
We can compute Grundy numbers for such a subtraction game. In a subtraction game with subtraction set {i} (only one move), the Grundy numbers are periodic: For positions 0,1,..., i-1: terminal, Grundy 0. For position i: can move to 0, so Grundy = mex{0} = 1. For position i+1: can move to 1 (if i+1 >= i) but 1 is terminal? Actually 1 is < i (since i>=1), so from 1 there is no move, Grundy(1)=0. So from i+1, the only move is to (i+1)-i = 1, which has Grundy 0, so Grundy(i+1) = mex{0} = 1. For i+2: move to 2, Grundy(2)=0, so Grundy=1. Continue up to 2i-1? Actually careful: For any x with i <= x < 2i, the only move is to x-i, which lies in [0, i-1], all Grundy 0, so Grundy(x) = mex{0} = 1. For x = 2i: moves to i (which Grundy 1). So Grundy(2i) = mex{1} = 0? But also could there be move to something else? Only subtract i, so only one move. So Grundy(2i) = mex{Grundy(i)} = mex{1} = 0. For x = 2i+1: move to i+1, Grundy(i+1)=1, so Grundy = mex{1}=0? But also maybe move to? Only one move. So Grundy(2i+1) = mex{1} = 0. For x = 3i: move to 2i, Grundy(2i)=0, so Grundy= mex{0}=1. So pattern: Grundy(x) = 0 if floor(x/i) is even? Let's compute:
Let q = floor(x / i) and r = x % i. Moves: from x, you can go to x - i = i*(q-1) + r (provided q>=1). So Grundy(x) depends on Grundy(x-i). Since it's a subtraction game with one move, the Grundy numbers are simply: Grundy(x) = 0 if q mod 2 == 0? Wait, we need to check.
We have base: for 0 <= x < i, q=0, Grundy=0. For i <= x < 2i, q=1, Grundy=1 (since mex of {0} = 1). For 2i <= x < 3i, q=2, Grundy? For x=2i, mex of {1}=0, for x=2i+1, mex of {1}=0, etc. So Grundy=0. For 3i <= x < 4i, q=3, Grundy=1. Thus indeed Grundy(x) = (q mod 2). Because for q even (including 0), Grundy=0; for q odd, Grundy=1.
But is that correct for all i? Let's verify with small i=1. Then the move is remove 1 stone each turn (always possible as long as stones >0). This is just normal Nim heap of size S, where each move removes 1 stone. The Grundy number of a heap of size S in subtraction game {1} is S mod 2? Actually the game where you can take exactly 1 stone each turn: The positions are 0: losing; 1: can move to 0, so winning; 2: can move to 1 (winning), so losing; 3: winning, etc. So Grundy(S) = S mod 2. Here q = S (since i=1, q = S). q mod 2 = S mod 2, matches.
For i=2: Subtraction game remove exactly 2. Then positions: 0,1 losing (0). 2: can move to 0 -> winning (Grundy 1). 3: can move to 1 -> winning (Grundy 1). 4: can move to 2 (Grundy 1) -> losing (Grundy 0). 5: move to 3 (Grundy 1) -> losing. 6: move to 4 (Grundy 0) -> winning. So pattern: Grundy = 1 if S mod 4 is 2 or 3? Actually 2:1, 3:1, 4:0,5:0,6:1,7:1,8:0,... So indeed Grundy(S) = 1 if floor(S/2) is odd? floor(S/2) is q. So if q odd (i.e., q mod 2 =1), Grundy=1; else 0. Which matches: q = floor(S/2). So q mod 2 determines Grundy.
Thus for any pile i, the Grundy number g_i(S) = ( floor(S / i) ) mod 2.
Now, the overall game is XOR of these bits? Since Grundy numbers are either 0 or 1? Actually floor(S/i) mod 2 yields 0 or 1. So each pile contributes a nim-heap of size either 0 or 1. The XOR of several bits is just the parity (XOR) of all those bits. So the whole game is winning for the first player if and only if the XOR (i.e., sum mod 2) of these bits is 1 (non-zero). So we can compute for each pile i: compute q = S_i // i (integer division), then b = q % 2. Then take XOR of all b. If XOR == 1, Alice (first player) wins; else Bob wins.
But is it truly that simple? Let's double-check with the sample:
Sample 1: N=1, pile1=1. i=1, floor(1/1)=1, odd => b=1 => XOR=1 => Alice wins. Output ALICE. Matches.
Sample 2: N=2, piles: 1 1. For i=1, S1=1 => b1=1. For i=2, S2=1 => floor(1/2)=0 => b2=0. XOR=1 => Alice wins. Output ALICE. Matches.
But we should consider if any pile's Grundy could be more than 1? Let's double-check: In a subtraction game with a single subtraction move, the Grundy numbers are indeed just 0 or 1, because the move options are only to one state (if legal). So the mex of a set containing at most one element is either 0 (if the set is empty, but it's never empty because if x>=i there is a move) or 1 if the set contains 0, or 0 if the set contains 1, etc. Since the set of reachable Grundy values is at most size 1, the mex will be either 0 or 1. So indeed Grundy is binary.
Thus overall XOR is just parity of number of piles with odd floor(S_i / i).
Wait, but careful: For piles where S_i < i, floor=0, even, so b=0. So those piles are losing positions (terminal) and contribute 0. So only piles with at least i stones matter, and specifically those with odd quotient contribute 1.
Thus answer: Alice wins if the number of piles with (S_i // i) % 2 == 1 is odd; else Bob wins.
But before concluding, we should consider if there is any nuance: Is it possible that a pile with S_i >= i but floor(S_i / i) even (like 2i) is a losing position (Grundy 0) for that pile. That is correct.
Now, can there be any other moves? The player chooses any pile i which has at least i stones, and removes exactly i stones. So the moves are exactly as described per pile.
Thus the solution appears straightforward.
But hold on: Are piles numbered from 1 to N, and the index i is the pile number, not the move selection? Yes. So each pile has its own index. So the subtraction amount is fixed for that pile. So indeed each pile is independent with its own subtraction set {i}. So the above reasoning holds.
Now the constraints: N <= 100, S_i <= 1000, T <= 100. So we can easily compute.
But we should test more cases to ensure no hidden complications.
Consider N=2, piles: 2 and 2. Pile1: floor(2/1)=2 even => b1=0. Pile2: floor(2/2)=1 odd => b2=1. XOR=1 => Alice wins. Let's simulate: piles: [2,2]. Alice's turn. She can pick pile2 (i=2) remove 2 -> pile2 becomes 0. Now piles: [2,0]. Now Bob's turn. Which piles have at least i? Pile1: has 2 >=1, so can remove 1 from pile1? But removal is exactly i stones, where i is the pile index. So from pile1 (index 1) you remove 1 stone. So Bob can remove 1 from pile1 -> pile1 becomes 1. Now piles: [1,0]. Alice's turn: Check pile1: has 1 >=1 -> can remove 1 -> pile1 becomes 0. Then no moves. Alice made last move, so Alice wins. Indeed matches.
Now test a case where XOR=0: N=2, piles: 1 and 2. Pile1: 1//1=1 odd -> b1=1. Pile2: 2//2=1 odd -> b2=1. XOR=0 => Bob wins. Simulate: [1,2]. Alice options: She can take from pile1: remove 1 -> pile1 becomes 0 => [0,2]. Now Bob's turn: piles: pile2 has 2>=2, so can remove 2 -> pile2 becomes 0 => no moves left, Bob made last move, Bob wins. Or Alice could take from pile2 first: remove 2 -> pile2 becomes 0 => [1,0]. Bob then can remove 1 from pile1 -> pile1 becomes 0 => Bob last move -> Bob wins. So Bob wins. Good.
What about piles where S_i is multiple of i but even multiple? e.g., N=1, pile1=2, i=1. floor(2/1)=2 even -> b=0 => XOR=0 => Bob wins? Let's simulate: one pile with 2 stones, each move remove 1. Alice removes 1 -> pile becomes 1; Bob removes 1 -> pile becomes 0, Bob last move, Bob wins. Yes.
Check pile with i=3, S=3: floor=1 odd -> b=1 => winning for first player if alone. Simulate: pile 3, allowed move: remove 3. Alice can remove 3 directly, pile becomes 0, Alice wins. That's winning. If S=6: floor=2 even -> b=0 => losing. Simulate: pile 6. Alice must remove 3 -> becomes 3. Bob then can remove 3 -> becomes 0, Bob wins. If Alice tries something else? Only remove 3. So indeed losing.
So seems correct.
But is there any scenario where a pile could have Grundy >1? No, because only one move.
Thus answer: XOR of ( (S_i // i) % 2 ) over i.
But wait, we must also consider that the pile numbers are from 1 to N, but they are fixed. So each pile's subtraction amount is its index. So that's fine.
Thus solution is O(T * N).
Now we should think about potential pitfalls: The problem states "There will be atleast 1 and atmost 1000 stones in any pile." So S_i up to 1000, and N up to 100. Division is fine.
But what about the possibility of choosing a pile i that has at least i stones. So the move is always to remove exactly i stones. It doesn't say you cannot choose the same pile multiple times, obviously you can.
Thus the analysis holds.
Now, before finalizing, we should verify with more edge cases: N=100, all piles have 0? But at least 1 stone per pile? Input says there will be atleast 1 and atmost 1000 stones in any pile. So S_i >=1.
What if a pile has S_i exactly equal to i? Then floor =1 odd -> b=1. If S_i = i-1, floor=0 even -> b=0.
What if a pile has S_i = 0? Not possible per constraints but could occur after moves.
All good.
Thus answer: compute XOR.
But wait: Is the game really the disjunctive sum? Yes, because each move affects exactly one pile, and the game ends when no moves are available in any pile. So standard impartial sum.
One more nuance: The move condition is "chooses any pile i which has atleast i stones in it". So if a pile i has at least i stones, you can remove i stones, but if it has less than i, you cannot. That's consistent.
Thus solution stands.
Now implement: For each test case, read N, then read N integers. Then compute ans = 0; for i from 1 to N: read s; q = s // i; if (q % 2) ans ^= 1; Finally print "ALICE" if ans==1 else "BOB".
But careful: The input lines: first line T, then for each test case, first line N, second line N numbers. So we need to parse accordingly.
Edge case: N may be up to 100, but the second line may have more or fewer numbers? It says N space separated integers, so it's N numbers.
All good.
Double-check sample: Input 2, then test1: N=1, next line "1". Test2: N=2, next line "1 1". Works.
Now, is there any possibility that the Grundy number is not just (s//i) % 2 because of some nuance about multiple moves? Let's formalize:
Define g(x) for pile i (fixed i). Recurrence: g(x) = mex{ g(x-i) } for x >= i; g(x)=0 for 0 <= x < i. Since g(x-i) is either 0 or 1 (by induction). So if x >= i, then the set contains exactly one element: g(x-i). Then mex of {0} = 1, mex of {1} = 0. So g(x) = 1 - g(x-i) for x >= i. With base g(x)=0 for x < i. This recurrence yields periodic pattern: for x in [k*i, (k+1)*i -1], g(x) = (k mod 2)? Actually: For k=0, g=0. For k=1, from i to 2i-1, g(x)=1 (since g(x-i) = 0). For k=2, from 2i to 3i-1, g(x) = 0 (since g(x-i)=1). So indeed g(x)=1 if floor(x/i) is odd, else 0. So yes.
Thus answer stands.
Now, could there be any other move like choosing pile i and removing i stones, but maybe you can also choose a pile and remove j stones if j is the index? No, the move says "chooses any pile i which has atleast i stones in it, and removes exactly i stones from it." So the index of the pile determines how many stones to remove. So no other options.
Thus solution is trivial.
But wait, the problem is from some contest, maybe there is a twist: The piles are numbered, but the player can choose any pile i (meaning any pile) and remove i stones, but i is the number of the pile, not the number of stones to remove? Actually it says "chooses any pile i which has atleast i stones in it, and removes exactly i stones from it." So yes, the number of stones removed equals the pile index.
Thus fine.
Now confirm with another example: Suppose N=3, piles: 3,3,3. Then pile1: 3//1=3 odd->b1=1; pile2: 3//2=1 odd->b2=1; pile3: 3//3=1 odd->b3=1. XOR = 1^1^1 = 1 -> Alice wins. Simulate? Might be messy but likely correct.
Suppose N=3: piles: 4,5,6. pile1: 4//1=4 even->0; pile2: 5//2=2 even->0; pile3: 6//3=2 even->0; XOR=0 -> Bob wins. Let's try a quick mental: initial [4,5,6]. Alice's options: She could take from pile1: remove 1 -> [3,5,6]. Then Bob... Hard to see but XOR 0 suggests Bob can win with perfect play. Could be.
Thus solution appears correct.
But we must ensure that the XOR of Grundy numbers is indeed the correct criterion for winning. Since the game is impartial and sum of independent components, the Nim-sum (XOR) of Grundy numbers determines the outcome. That's standard.
Thus answer: compute XOR of bits.
Implementation: For each test case:
- read N.
- read line of N integers (maybe across multiple lines? Usually it's one line, but we can just read tokens.)
- for i from 1 to N: s = next int bit = (s // i) & 1 xor_result ^= bit
- print "ALICE" if xor_result == 1 else "BOB"
Complexity: O(T*N).
Now test with sample: Output matches.
Now consider T up to 100, N up to 100, fine.
Edge Cases:
-
N=100, all piles large. Works.
-
Might have trailing spaces etc. Handle reading.
Now, is there any scenario where the Grundy number is not binary because of multiple moves? Actually in this game, from a given pile, there is exactly one move (subtract i) if possible, else none. So only one move. So Grundy is binary.
But what about the possibility of picking the same pile multiple times? That's just a sequence of moves. But each move is independent. So the game graph is a simple path: x -> x-i -> x-2i -> ... until remainder < i. So Grundy numbers along the path alternate.
Thus fine.
Therefore answer is straightforward.
But before finalizing, let me consider if there could be any misinterpretation: The problem says "Alice and Bob play alternately, with Alice starting. In a turn, the player chooses any pile i which has atleast i stones in it, and removes exactly i stones from it." It doesn't explicitly say that i is the index of the pile, but says "any pile i", implying the piles are labeled i. So yes.
Thus solution is done.
Now I'll provide explanation in solution: Each pile is an impartial game with Grundy = (S_i / i) mod 2 (integer division). XOR of these bits decides winner.
I'll produce Python code to solve.
But careful: Input reading might need to handle multiple test cases and possible extra lines. I'll use sys.stdin.read() to get all integers.
Pseudo:
import sys
def main(): data = list(map(int, sys.stdin.read().split())) it = iter(data) T = next(it) out = [] for _ in range(T): N = next(it) xor = 0 for i in range(1, N+1): s = next(it) if (s // i) % 2 == 1: xor ^= 1 out.append("ALICE" if xor else "BOB") sys.stdout.write("\n".join(out))
if name == "main": main()
That's it.
But wait, is there any catch with large N and large S that might cause integer overflow? No.
Now, I'll double-check with some random cases using brute-force recursion for small values to ensure the XOR formula works.
Let's do mental for N=2, all small S.
We can enumerate state (a,b) but Grundy of sum? Actually we can compute the outcome (winning for first player) by checking if XOR of Grundy bits is non-zero. Let's test some manual:
Case: N=2, i=1 and i=2, S1, S2.
Compute Grundy1 = floor(S1/1) mod 2 = S1 mod 2. Grundy2 = floor(S2/2) mod 2.
XOR = (S1 mod 2) ^ ( (S2//2) mod 2).
We'll brute small S1 (0..3), S2 (0..5) maybe, and see if the outcome matches known impartial game outcomes? Since we can compute using recursion for sum? Let's do mental for a few:
We'll denote state (S1,S2). Moves: from pile1: if S1>=1, new state (S1-1,S2). From pile2: if S2>=2, new state (S1,S2-2). Terminal when no moves: that is S1<1 and S2<2.
We can compute Grundy for sum as XOR of Grundy numbers. Let's manually compute outcomes for first player (winning if XOR!=0). We'll test a few:
S1=0,S2=0: No moves, losing. Grundy1=0, Grundy2=0, XOR=0 -> losing. Good. S1=1,S2=0: From (1,0): can move from pile1 -> (0,0) losing, so (1,0) winning. Grundy1=1, Grundy2=0, XOR=1 -> winning. Good. S1=0,S2=1: No move (since S2<2), losing. Grundy1=0, Grundy2=0 (1//2=0) -> XOR=0. Good. S1=0,S2=2: Move from pile2 -> (0,0) losing, so winning. Grundy1=0, Grundy2=1 (2//2=1) -> XOR=1 -> winning. Good. S1=0,S2=3: Move from pile2 -> (0,1) losing? (0,1) is terminal? Actually (0,1) S2=1<2, no moves, so losing. So (0,3) winning. Grundy1=0, Grundy2= floor(3/2)=1 mod2=1 -> XOR=1 -> winning. Good. S1=0,S2=4: Move from pile2 -> (0,2) which is winning (since from (0,2) you can move to (0,0) and win). So (0,4) move to winning state, so (0,4) losing if all moves go to winning. Also check if there is any other move? Only pile2. So (0,4) losing. Grundy1=0, Grundy2= floor(4/2)=2 mod2=0 -> XOR=0 -> losing. Good. S1=1,S2=1: (1,1): Moves: from pile1 -> (0,1) which is losing? (0,1) no moves -> losing, so (1,1) winning because you can move to losing. Also from pile2? S2=1<2, so no. So winning. Grundy1=1, Grundy2=0 -> XOR=1 -> winning. Good. S1=1,S2=2: (1,2): Moves: from pile1 -> (0,2) which is winning (as above). From pile2 -> (1,0) which is winning (since (1,0) winning). So all moves go to winning positions, so (1,2) losing. Grundy1=1, Grundy2=1 -> XOR=0 -> losing. Good. S1=1,S2=3: (1,3): Moves: pile1 -> (0,3) winning; pile2 -> (1,1) winning? (1,1) is winning (as above). So both to winning, so (1,3) losing? Let's check: (0,3) we determined winning; (1,1) winning; so losing. Grundy1=1, Grundy2= floor(3/2)=1 mod2=1 -> XOR=0 -> losing. Good. S1=1,S2=4: (1,4): Moves: pile1 -> (0,4) losing? (0,4) we determined losing. So from (1,4) we have a move to losing state, thus (1,4) winning. Also pile2 -> (1,2) losing? (1,2) we determined losing. So also a move to losing. So winning. Grundy1=1, Grundy2= floor(4/2)=2 mod2=0 -> XOR=1 -> winning. Good. S1=2,S2=0: (2,0): Moves: pile1 -> (1,0) winning, so (2,0) losing? Also can move again? Only one move per turn. So (2,0) move to winning, thus losing. Grundy1=0 (2//1=2 even), Grundy2=0 -> XOR=0 -> losing. Good. S1=2,S2=1: (2,1): Moves: pile1 -> (1,1) winning; pile2? S2=1<2 no. So all moves to winning -> losing. Grundy1=0, Grundy2=0 -> XOR=0 -> losing. Good. S1=2,S2=2: (2,2): Moves: pile1 -> (1,2) losing? (1,2) we determined losing. So (2,2) winning because can move to losing. Also pile2 -> (2,0) losing? (2,0) losing. So winning. Grundy1=0, Grundy2=1 -> XOR=1 -> winning. Good. S1=2,S2=3: (2,3): Moves: pile1 -> (1,3) losing? (1,3) losing; pile2 -> (2,1) losing. So winning. Grundy1=0, Grundy2=1 -> XOR=1 -> winning. Good. S1=2,S2=4: (2,4): Moves: pile1 -> (1,4) winning; pile2 -> (2,2) winning. So losing. Grundy1=0, Grundy2=0 -> XOR=0 -> losing. Good. S1=3,S2=0: (3,0): Moves: pile1 -> (2,0) losing -> winning. Grundy1=1, Grundy2=0 -> XOR=1 -> winning. Good. S1=3,S2=1: (3,1): Moves: pile1 -> (2,1) losing -> winning. Grundy1=1, Grundy2=0 -> XOR=1 -> winning. Good. S1=3,S2=2: (3,2): Moves: pile1 -> (2,2) winning; pile2 -> (3,0) winning; so losing. Grundy1=1, Grundy2=1 -> XOR=0 -> losing. Good. S1=3,S2=3: (3,3): Moves: pile1 -> (2,3) winning; pile2 -> (3,1) winning; so losing? Check (2,3) we determined winning; (3,1) winning; so losing. Grundy1=1, Grundy2=1 -> XOR=0 -> losing. Good. S1=3,S2=4: (3,4): Moves: pile1 -> (2,4) losing -> winning; pile2 -> (3,2) losing -> winning. So winning. Grundy1=1, Grundy2=0 -> XOR=1 -> winning. Good.
All matches. So formula holds.
Thus solution is correct.
Now we should consider: Are we missing the possibility of different indexing (0-indexed)? The problem says piles are numbered from 1 to N, so i starts at 1.
Thus final answer.
Now I'll produce final solution.
But the problem might be from some contest where participants may think it's Nim with Grundy numbers but they need to compute. It's straightforward.
Thus final answer: Compute XOR of (S_i // i) mod 2.
Will produce code in Python.
Implementation details: Use reading all ints.
Time complexity O(T*N).
Now output as required.
Edge case: T up to 100, N up to 100, so at most 10,000 numbers, trivial.
Now finalize.
But before concluding, let's consider a potential twist: The move "chooses any pile i which has atleast i stones in it, and removes exactly i stones from it." What if there are piles with index > N? No.
All good.
Thus solution final.
Will provide explanation in final output: For each pile i, the Grundy number is (S_i / i) mod 2. XOR tells winner.
One more check: Could there be a scenario where the piles are not independent because the move selection might depend on the indices themselves? No, they are independent.
Thus answer.
Now I'll write final answer. ```python
import sys
def solve() -> None: data = list(map(int, sys.stdin.read().split())) it = iter(data) t = next(it) out_lines = [] for _ in range(t): n = next(it) xor_sum = 0 for i in range(1, n + 1): s = next(it) if (s // i) & 1: # (s // i) % 2 == 1 xor_sum ^= 1 out_lines.append("ALICE" if xor_sum else "BOB") sys.stdout.write("\n".join(out_lines))
if name == "main": solve()