시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 20 | 13 | 12 | 63.158% |
Alice and Bob are playing a game.
They have n piles of stones, such that there are ai (1 ≤ ai ≤ n) stones in the i-th pile.
During his/her turn, each player, starting from Alice, will pick any pile and take at least one and at most x stones from it.
The player that can’t make a move on his/her turn (all piles are empty) loses.
Alice and Bob still have not decided the final value of x, so they have asked you to find out who will win if both players play optimally for all values of x, such that 1 ≤ x ≤ n.
The first line of input contains one integer n (1 ≤ n ≤ 500 000): the number of piles and the upper bound on the number of stones in piles.
The next line contains n integers, a1, a2, . . . , an (1 ≤ ai ≤ n): the number of stones in piles.
Print n words, where the i-th of them is “Alice” if Alice will win under optimal play for i = x, and “Bob” otherwise.
6 6 6 6 6 6 6
Bob Bob Bob Bob Bob Bob
4 1 2 3 4
Bob Alice Bob Alice
5 1 2 3 2 2
Bob Alice Bob Bob Bob
In the first example, independently on x, Bob may do symmetrical moves (the same move on the pile with the same number of stones), so on each turn, he definitely will have at least one available move.
Camp > Petrozavodsk Programming Camp > Winter 2020 > Day 3: 300iq Petrozavodsk Contest III E번