시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 172 | 86 | 81 | 51.592% |
Alice and Bob are playing a turn-based game. The rules of the game are as follows:
10
, 110
, 100
, 1010
. Then the player has to reverse $t$. For example, if $s = $010101
, the player can select substring $t = $1010
and reverse it, obtaining $s = $001011
Which player has the winning strategy, if Alice moves first?
A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
The only line of the input contains a binary string $s$ ($1 \le |s| \le 10^6$) — the string with which Alice and Bob play.
If Alice wins, output Alice
. Otherwise, output Bob
.
010
Alice
1111
Bob
1010
Bob
1010001011001
Alice
In the first sample, Alice can choose substring 10
of 010
and reverse it, obtaining string 001
. Bob can’t make any move with this string, and loses.
In the second sample, Alice can’t make a single move and loses.