/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
N 行 N 列のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。マス (i,j) にははじめ A_{i,j} 個の石があります。
Alice と Bob がこのグリッドを使って以下のようなゲームを行います。
- Alice から始めて両者は交互に手番をプレイする。
- 各手番では、プレイヤーはマスを 1 つ選び、そこから 1 個以上 K 個以下の石をまとめて上または左に隣接するマスへ移動させる。具体的には、次の手順を順に行う。
- 石が 1 個以上あるマス (i,j) を選ぶ。ただし、マス (1,1) は選べない。
- マス (i,j) にある石の個数を c とし、1 \le x \le \min(c,K) を満たす整数 x を選ぶ。
- 移動先として、存在するならばマス (i-1,j) またはマス (i,j-1) のいずれか一方を選び、マス (i,j) から石を x 個取り出して全てそのマスに移動させる。
先に手番をプレイできなくなったプレイヤーの負けです。
両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T
- 2\le N\le 100
- 1\le K\le 10^9
- 0\le A_{i,j}\le 10^9
- 全てのテストケースにおける N^2 の総和は 3\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N K
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、両者が最善を尽くしたとき Alice が勝つならば Alice を、Bob が勝つならば Bob を出力せよ。
入力例 1
3 2 2 0 1 3 2 3 1 1 1 1 1 1 1 1 1 1 4 4 3 8 5 3 4 2 0 6 0 9 10 4 1 9 7 10
出力例 1
Alice Bob Alice
1 番目のテストケースについて考えます。
例えばゲームは以下のように進行します（両者が最適に手番をプレイしているとは限らないことに注意してください）：
- Alice の手番：マス (2,2) を選び、石を 2 個取り出す。取り出した石をマス (1,2) に移動させる。
- Bob の手番：マス (1,2) を選び、石を 2 個取り出す。取り出した石をマス (1,1) に移動させる。
- Alice の手番：マス (2,1) を選び、石を 2 個取り出す。取り出した石をマス (1,1) に移動させる。
- Bob の手番：マス (2,1) を選び、石を 1 個取り出す。取り出した石をマス (1,1) に移動させる。
- Alice の手番：マス (1,2) を選び、石を 1 個取り出す。取り出した石をマス (1,1) に移動させる。
- Bob の手番：Bob は手番をプレイできないので負けである。
Alice は最善を尽くすことで必ず Bob に勝つことができます。したがって、1 行目には Alice を出力してください。
Score : 500 points
Problem Statement
There is an N \times N grid. The cell at the i-th row from the top and the j-th column from the left is denoted as cell (i,j). Cell (i,j) initially contains A_{i,j} stones.
Alice and Bob play the following game using this grid.
- Starting with Alice, the two players alternate taking turns.
- On each turn, the player chooses a cell and moves at least 1 and at most K stones from it together to an adjacent cell above or to the left. Specifically, the following steps are performed in order:
- Choose a cell (i,j) that contains at least 1 stone. Cell (1,1) cannot be chosen.
- Let c be the number of stones in cell (i,j), and choose an integer x satisfying 1 \le x \le \min(c,K).
- Choose as the destination either cell (i-1,j) (if it exists) or cell (i,j-1) (if it exists), then remove x stones from cell (i,j) and move all of them to that cell.
The player who cannot take a turn first loses.
Determine which player wins when both play optimally.
You are given T test cases; solve each of them.
Constraints
- 1\le T
- 2\le N\le 100
- 1\le K\le 10^9
- 0\le A_{i,j}\le 10^9
- The sum of N^2 over all test cases is at most 3\times 10^5.
- 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 K
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
Output
Output the answers for the test cases in order, separated by newlines.
For each test case, output Alice if Alice wins when both play optimally, and Bob if Bob wins.
Sample Input 1
3 2 2 0 1 3 2 3 1 1 1 1 1 1 1 1 1 1 4 4 3 8 5 3 4 2 0 6 0 9 10 4 1 9 7 10
Sample Output 1
Alice Bob Alice
Consider the first test case.
For example, the game may proceed as follows (note that the players are not necessarily playing optimally):
- Alice's turn: Choose cell (2,2) and remove 2 stones. Move the removed stones to cell (1,2).
- Bob's turn: Choose cell (1,2) and remove 2 stones. Move the removed stones to cell (1,1).
- Alice's turn: Choose cell (2,1) and remove 2 stones. Move the removed stones to cell (1,1).
- Bob's turn: Choose cell (2,1) and remove 1 stone. Move the removed stone to cell (1,1).
- Alice's turn: Choose cell (1,2) and remove 1 stone. Move the removed stone to cell (1,1).
- Bob's turn: Bob cannot take a turn and loses.
By playing optimally, Alice can always beat Bob. Thus, output Alice on the first line.