問題一覧 > 通常問題

No.1016 三目並べ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 135
作問者 : 👑 maspymaspy / テスター : 👑 beetbeet
14 ProblemId : 4015 / 出題時の順位表
問題文最終更新日: 2020-03-30 10:30:50

問題文

$O$ さんと $X$ さんは、$1\times N$ のマス目を使ってゲームをしています。 ゲームは $O$ さんの手番から始まり、次のように進行します。

  1. $O$ さんは、未だ記号の書き込まれていないマスをひとつ選び、記号「o」を書き込む。
  2. $X$ さんは、未だ記号の書き込まれていないマスをひとつ選び、記号「x」を書き込む。
  3. 全てのマスに記号が書き込まれるまで、1, 2を繰り返す。
全てのマスに記号が書き込まれたあと、$3$ マス続けて記号「o」が書き込まれた場所が存在すれば $O$ さんの勝ち。 そうでなければ $X$ さんの勝ちとします。

このゲームが途中まで進行しており、途中経過の盤面が文字列 $S$ で与えられます。 次は $O$ さんの手番です。 両者が最善を尽くすとき、どちらが勝つかを判定してください。

$T$ 件の盤面が与えられるので、それぞれについて判定してください。

入力

$T$
$N_1 \ S_1$
$N_2 \ S_2$
$\vdots$
$N_T \ S_T$
  • $T$ は正の整数で、$1\leqq T\leqq 100$ を満たす。
  • $N_i$ は正の整数で、$1\leqq N_i\leqq 1000$ を満たす。
  • $S_i$ は長さ $N_i$ の文字列で、文字 o, x, - からなる。 o, x はこれまでにそのマスに書き込まれた記号を表しており、- はそのマスに未だ記号が書き込まれていないことを表している。
  • $S_i$ は同数の o, x を含む(したがって次は $O$ さんの手番である)ことが保証される。

出力

$i$ 行目に、盤面 $S_i$ の場合の勝者の名前(O または X)を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
7
10 xxoo--xxoo
10 oo-ooxxxx-
10 ooxxo--oxx
10 xooo--xx--
6 oooxxx
6 oxoxox
1 -
出力
O
O
X
O
O
X
X

$1$ つめの盤面 xxoo--xxoo において、$O$ さんが左側の空マスに o を書き込むと、 ゲーム終了時にはマス目が xxoooxxxoo となり、$O$ さんの勝利条件が満たされています。

$2$ つめの盤面の場合には、$O$ さんが左側の空マスに o を書き込むと、 ゲーム終了時にはマス目が oooooxxxxx となります。o が $5$ マス続けて並びますが、この場合にも $O$ さんの勝利条件は満たされています。

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