D - mod M Game

Contest Duration: 2022-09-11(Sun) 12:00 - 2022-09-11(Sun) 14:00 (local time) (120 minutes) Back to Home

D - mod M Game Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $700$ 点

問題文

黒板に $2N$ 個の整数 $A_1, A_2, ..., A_{2N}$ が書かれています。また、 $2$ 以上の整数 $M$ があります。
Alice と Bob はゲームをします。ゲームは Alice を先攻として、黒板の上の数が全てなくなるまで次の操作を交互に行います。

数を $1$ 個選び、その数を黒板から消す。

ゲームを終了した時点で、(Alice が消した数の和) $\text{mod }M$ と (Bob が消した数の和) $\text{mod }M$ が一致していれば Bob の勝ち、そうでない場合は Alice の勝ちです。
両者が最善を尽くしたとき、どちらが勝ちますか？

制約

$1 \leq N \leq 2 \times 10^5$
$2 \leq M \leq 10^9$
$0 \leq A_i \leq M - 1$
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $A_1$   $A_2$   $\dots$   $A_{2N}$

出力

Alice が勝つ場合は Alice を、Bob が勝つ場合は Bob を出力せよ。

入力例 1Copy

Copy

2 9
1 4 8 5

出力例 1Copy

Copy

Alice

ゲームの進行例として次のようなものが考えられます。

Alice が $1$ を消す。
Bob が $4$ を消す。
Alice が $5$ を消す。
Bob が $8$ を消す。

このように進んだ場合、(Alice が消した数の和) $\text{mod }M$ は $(1 + 5) \bmod 9 = 6$ , (Bob が消した数の和) $\text{mod }M$ は $(4 + 8) \bmod 9 = 3$ で、 $6 \neq 3$ なので Alice の勝ちです。

入力例 2Copy

Copy

3 998244353
1 2 3 1 2 3

出力例 2Copy

Copy

Bob

Score : $700$ points

Problem Statement

There are $2N$ integers $A_1, A_2, ..., A_{2N}$ written on a blackboard, and an integer $M$ at least $2$ .
Alice and Bob will play a game. They will alternately perform the following operation, with Alice going first, until there is no number on the blackboard.

Choose a number and delete it from the blackboard.

At the end of the game, if the sum of numbers deleted by Alice modulo $M$ equals the sum of numbers deleted by Bob modulo $M$ , Bob wins; otherwise, Alice wins.
Which player will win if both plays optimally?

Constraints

$1 \leq N \leq 2 \times 10^5$
$2 \leq M \leq 10^9$
$0 \leq A_i \leq M - 1$
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

 $N$   $M$ 
 $A_1$   $A_2$   $\dots$   $A_{2N}$

Output

If Alice wins, print Alice; if Bob wins, print Bob.

Sample Input 1Copy

Copy

2 9
1 4 8 5

Sample Output 1Copy

Copy

Alice

The game may proceed as follows.

Alice deletes $1$ .
Bob deletes $4$ .
Alice deletes $5$ .
Bob deletes $8$ .

In this case, the sum of numbers deleted by Alice modulo $M$ is $(1 + 5) \bmod 9 = 6$ , and the sum of numbers deleted by Bob modulo $M$ is $(4 + 8) \bmod 9 = 3$ . Since $6 \neq 3$ , Alice wins.

Sample Input 2Copy

Copy

3 998244353
1 2 3 1 2 3

Sample Output 2Copy

Copy

Bob