/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 1100 点
問題文
正整数 N,X,Y と長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
石の山が N 個あり、 i 番目 (1\le i\le N) の山には A_i 個の石が積まれています。
Alice と Bob がこれらの山を使って以下のようなゲームを行います。
- Alice から始めて両者は交互に手番をプレイする。
- 各手番では、プレイヤーは空でない山を一つ選び、その山から 1 個か 2 個石を取り除く。ただし、取り除いた後にその山の石の個数が X の倍数または Y の倍数となるような行動を取ることはできない。
先に手番をプレイできなくなったプレイヤーの負けです。
両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T \le 2\times 10^5
- 1\le N \le 2\times 10^5
- 全てのテストケースにおける N の総和は 2\times 10^5 以下
- 1\le X < Y\le 10^9
- 1\le A_i \le 10^{18}
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N X Y A_1 A_2 \ldots A_N
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、両者が最善を尽くしたとき Alice が勝つならば Alice を、Bob が勝つならば Bob を出力せよ。
入力例 1
3 2 3 5 4 12 5 1 2 1 2 3 4 5 6 530 879 17031 42909 97721 34323 39597 26999
出力例 1
Alice Bob Alice
1 つ目のテストケースについて考えます。
例えばゲームは以下のように進行します。
- Alice が 1 番目の山から石を 2 個取り除く。 1 番目の山の石は残り 2 個となる。
- Bob が 2 番目の山から石を 1 個取り除く。 2 番目の山の石は残り 11 個となる。
- Alice が 1 番目の山から石を 1 個取り除く。 1 番目の山の石は残り 1 個となる。
- Bob は手番をプレイできないので、Bob の負けであり Alice の勝ちとなる。
このテストケースでは両者がどのように手番をプレイしても Alice が必ず勝ちます。したがって、 1 行目には Alice と出力してください。
Score : 1100 points
Problem Statement
You are given positive integers N, X, Y and a length-N integer sequence A=(A_1,A_2,\ldots,A_N).
There are N piles of stones, and the i-th pile (1\le i\le N) has A_i stones.
Alice and Bob will play the following game using these piles:
- Starting with Alice, the two players take turns alternately.
- In each turn, the player chooses one non-empty pile and removes one or two stones from that pile. However, the player cannot make a move such that the number of stones in that pile becomes a multiple of X or a multiple of Y after removing stones.
The player who cannot make a move first loses.
Determine which player wins when both players play optimally.
You are given T test cases, solve each of them.
Constraints
- 1\le T \le 2\times 10^5
- 1\le N \le 2\times 10^5
- The sum of N over all test cases is at most 2\times 10^5.
- 1\le X < Y\le 10^9
- 1\le A_i \le 10^{18}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N X Y A_1 A_2 \ldots A_N
Output
Output the answers for each test case in order, separated by newlines.
For each test case, print Alice if Alice wins when both players play optimally, and Bob if Bob wins.
Sample Input 1
3 2 3 5 4 12 5 1 2 1 2 3 4 5 6 530 879 17031 42909 97721 34323 39597 26999
Sample Output 1
Alice Bob Alice
Consider the first test case.
For example, the game proceeds as follows:
- Alice removes two stones from the first pile. The first pile has two stones remaining.
- Bob removes one stone from the second pile. The second pile has eleven stones remaining.
- Alice removes one stone from the first pile. The first pile has one stone remaining.
- Bob cannot make a move, so Bob loses and Alice wins.
In this test case, Alice always wins no matter how both players make their moves. Therefore, print Alice on the first line.