問題一覧 > 通常問題

No.2760 not fair position game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 82
作問者 : nikoro256nikoro256 / テスター : 👑 binapbinap matcharate12matcharate12 aplysiaSheepaplysiaSheep
1 ProblemId : 10900 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-05-16 00:51:59

問題文

AliceとBobは陣取りゲームをすることにしました。
陣取りゲームは縦$N$行横$N$列のグリッド上で行われます。上から$i$行目左から$j$列目のマスを$(i,j)$で表します。
Aliceが塗る色は赤、Bobが塗る色は黒とします。
最初グリッド上はAliceのスタート地点は赤でBobのスタート地点は黒で塗られており、そのマス以外は色が塗られていない無色の状態です
Aliceのスタート地点は$(K,1)$からBobのスタート地点は$(K,N)$とし、Aliceを先手として以下の動作を繰り返すこととします。

  • 隣接している一つのマスに移りそのマスの色を自分の色にする。（ただし自分の色ではない色が塗られているマス、つまり相手の色が塗られているマスには移ることはできません。）


    • $10^{18} +N^2$ターンだけゲームを続けた時終了とし、赤が多いならAliceの勝利、そうでないならならBobの勝利とします。
    両者が最善を尽くした時、Aliceが勝つならAliceとBobが勝つならBobと出力して下さい

    入力

    $N$ $K$

  • $2 \le N \leq 10^5$
  • $1 \le K \leq N$

    • 出力

    Aliceが勝つならAliceとBobが勝つならBobと出力して下さい

    サンプル

    サンプル1
    入力
    2 1
    出力
    Bob

    Aliceは$(1,1)$、Bobは$(1,2)$から動き始めます。
    よって最初$(1,1)$は赤、$(2,2)$は黒で塗られています。
    最初のターンAliceは$(1,1)$におり、$(1,2)$は既に黒で塗られているため、Aliceは$(2,1)$のマスのみに動くことが出来ます。
    次のターンBobは$(1,2)$におり、$(1,1)$は既に赤で塗られているため、Bobは$(2,2)$のマスのみに動くことが出来ます。
    この後もターンが続きますが、双方自分の色のマスの上のみ動くことが出来るため新しく色が塗り替わることはありません。
    よって赤$2$マス黒$2$マスでBobの勝利となります。

    サンプル2
    入力
    5 2
    出力
    Alice

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。