各文字列のゲームの値を求めていきます。

A を \(+1\) に、B を \(-1\) に対応させて文字列を各要素が \(\pm 1\) の整数列と対応つけます。

まず、文字列が有限長である場合を考えます。

文字列 \(S\) が有限長である場合は、その長さを \(n\) とし、\(S_1\neq S_k\) を満たす最小の \(k\) （存在しない場合は \(k=n+1\) とする）に対してゲームの値は \(\displaystyle (k-1)A_1+\sum_{i=k}^n \frac{A_i}{2^{i-k+1}}\) と表せます（ただし、\(A\) は \(S\) と対応つけられた整数列）

文字列が無限長である場合、ほとんどの場合上で用いた方法を無限に拡張することでゲームの値を計算できますが、全て A の場合や途中から全て A の場合などに例外が発生します。

具体的には、以下のようにして無限長の文字列 \(S\) に対するゲームの値を計算することができます：

• \(S\) の文字が全て A のとき：\(\omega\)
• \(S\) の文字が全て B のとき：\(-\omega\)
• \(S\) に A, B が両方無限回現れるとき：\(\displaystyle (k-1)A_1+\sum_{i=k}^\infty \frac{A_i}{2^{i-k+1}}\)
• \(S\) が両方の文字を含み、途中から全て A のとき：\(\displaystyle (k-1)A_1+\sum_{i=k}^\infty \frac{A_i}{2^{i-k+1}} -\varepsilon\)
• \(S\) が両方の文字を含み、途中から全て B のとき：\(\displaystyle (k-1)A_1+\sum_{i=k}^\infty \frac{A_i}{2^{i-k+1}} +\varepsilon\)

ここで、\(\omega,\varepsilon\) はそれぞれ無限大・無限小を表します。\(\omega\) は全ての非負整数より大きい最も単純な数として定義され、\(\varepsilon\) は全ての正の実数より小さい、最も単純な正の数と定義されます。

これらを元に計算すると、有理数 \(C_1,C_2,C_3\) を用いてゲームの値の和は \(C_1\omega + C_2 + C_3\varepsilon\) と表されます。そのようなゲームで Alice が勝つことは辞書順で \((C_1,C_2,C_3)>(0,0,0)\) となることと同値です。

以上を適切に実装することでこの問題に正答することができます。