ゲームの結合和に関する問題です。

\(N\) 個の不偏ゲーム \(G_1,G_2,\ldots,G_N\) の結合和 とは、各手番で \(N\) 個のゲーム全てに着手するゲームと定義されます。

本問題であれば、\(G_i\) は最初 \(A_i\) 個の石があり、各手番では石を\(1\) 個以上 \(B_i\) 個以下取り除くゲームと定義した時の \(N\) 個の結合和として得られるゲームの勝敗判定ができれば良いです。

そして、結合和の勝敗判定は以下のように行うことができます：

• ゲームの局面 \(G\) の遠隔度 \(\mathscr{R}(G)\) を以下のように定義する：
  • \(G\) が終了盤面であるとき：\(\mathscr{R}(G)=0\)
  • \(\mathscr{R}(G')\) が偶数となる \(G\to G'\) が存在するとき：\(\mathscr{R}(G)=1+\min\lbrace\mathscr{R}(G') \ |\ G\to G',\mathscr{R}(G')\ は偶数\rbrace\)
  • \(G\) が終了盤面ではなく、\(\mathscr{R}(G')\) が偶数となる \(G\to G'\) が存在しないとき：\(\mathscr{R}(G)=1+\max\lbrace\mathscr{R}(G') \ |\ G\to G'\rbrace\)
• このとき、\(\displaystyle \min_{1\le i\le N}\mathscr{R}(G_i)\) が奇数ならば先手必勝、偶数ならば後手必勝である。

石が \(A\) 個あり、\(1\) 回で石を \(1\) 個以上 \(B\) 個以下取れるようなゲームの遠隔度を考えます。

\(A\) を \(B+1\) で割った商とあまりをそれぞれ \(q,r\) とします。このとき、遠隔度は \(r=0\) なら \(2q\) 、\(r>0\) なら \(2q+1\) と表すことができます。

証明は帰納法で行うことができます。

以上より、\(N\) 個のゲームそれぞれについて遠隔度を計算し、その最小値の偶奇を元に判定することができます。

実装例(Python3)

import sys

input = sys.stdin.readline
INF = 10**9 + 2026
for _ in range(int(input())):
    n = int(input())
    q, r = INF, INF
    for i in range(n):
        a, b = map(int, input().split())
        qq, rr = a // (b + 1), a % (b + 1)
        if q > qq:
            q = qq
            r = INF
        if q == qq:
            r = min(r, rr)
    print("Alice" if r != 0 else "Bob")