Chord Triangle Game

解説

$N\bmod 4=2$ なら Alice、それ以外なら Bob が勝ちます。

弦で区切られた異なる領域の点を結ぶことはできないため、各領域に残る未使用の点の数を考えます。 Alice が点数 $m$ の領域に弦を引くと、その両側の点数は $a+b=m-2$ となります。 Bob は片側から点を選び、その側をさらに二つの領域に分けます。

点数が $4k+2$ の領域がある場合、Alice は勝てます。

点数が $2$ なら、その二点を結ぶだけで Bob は操作できません。 点数が $6$ 以上なら、Alice は両側の点数が $2$ と $4k-2$ になるように弦を引きます。 どちらも $4$ で割った余りが $2$ なので、Bob がどちら側を選んでも、もう片側に同じ条件の領域が残ります。 これを繰り返すと、点数が減り続け、最後には点数 $2$ の領域で勝てます。

逆に、そのような領域がない場合、Bob はその状態を維持して勝てます。

Alice が弦を引いた両側の点数を $a,b$ とします。 元の点数は $4$ で割った余りが $2$ ではないので、$a,b$ がともに余り $2$ になることはありません。 Bob は余り $2$ の側があればそちらを、なければ点が残っている側を選びます。

選んだ側の点数を $s\ge1$ とすると、Bob は点 $C$ の位置を調整して、残る二領域の点数を次のようにできます。

• $s\bmod4=3$ なら、$1$ と $s-2$。
• それ以外なら、$0$ と $s-1$。

いずれも余り $2$ の領域は生じません。 したがって Bob は常に操作でき、いずれ Alice が操作できなくなります。

計算量はテストケースごとに $O(1)$ です。