| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 155 | 82 | 75 | 56.391% |
There are $N$ stone piles, numbered by sequential integers from 1ドル$ to $N$. The $i$-th pile contains $a_i$ stones. Additionally, each pile $i$ has an integer $b_i$ associated with it.
Alice and Bob play the following game using those stone piles.
They are alternately performing the following operation: choose pile $i$ and a nonnegative integer $k$ such that $b_i^k$ is not greater than the current number of stones in pile $i,ドル and remove $b_i^k$ stones from pile $i$. If a player cannot do that on their turn, the opposite player wins.
Alice moves first. Determine who will win if both players are playing optimally.
The first line of input contains one integer $N$ (1ドル \le N \le 10^5$), the number of piles. The $i$-th of the following $N$ lines contains two integers $a_i$ and $b_i$ (1ドル \le a_i, b_i \le 10^9$): the initial number of stones in the $i$-th pile and the integer associated with it, respectively.
If Alice wins the game when both sides are playing optimally, print "Alice". Otherwise, print "Bob".
2 10 3 7 4
Bob
16 903 5 246 38 884 12 752 10 200 17 483 6 828 27 473 21 983 35 953 36 363 35 101 3 34 23 199 8 134 2 932 28
Alice
16 35 37 852 17 789 37 848 40 351 27 59 32 271 11 395 20 610 3 631 33 543 14 256 28 48 8 277 24 748 38 109 40
Bob