Company: Zorvyn SDE_4april
Difficulty: medium
10 marks 2s limit 256MB Problem Statement Alice and Bob are playing a strategic stone game. There are N piles of stones, where pile i contains A[i] stones. Players take turns, with Alice going first. On each turn, a player must: Choose a non-empty pile. Remove at least 1 stone and at most half (rounded down) of the stones from that pile. Exception: If a pile has only 1 stone, the player must remove that 1 stone. The player who removes the last stone from the last pile wins. Both players play optimally. Determine who wins. Input Format First line contains a single integer N . . Second line contains N space-separated integers A[1], A[2], ..., A[N] . Output Format Print "Alice" if Alice wins, "Bob" if Bob wins. Examples Example 1 Input: 1 1 Output: Alice Explanation: Alice takes the only stone and wins. Example 2 Input: 1 2 Output: Bob Explanation: Alice can only take 1 stone (half of 2, rounded down). Bob takes the remaining 1 stone and wins. Example 3 Input: 1 3 Output: Alice Explanatio