Simple Othello

Time Limit : 2 sec, Memory Limit : 65536 KB

B - 簡易オセロ

問題文

B君はオセロが大好きである (オセロのルールについてはWikipediaのオセロのページを参照せよ.「パス」についても Wikipedia に書かれているとおり,駒を打つことができない場合のみパスできるものとし,パスの回数に制限は無いものとする.) B君は駒の初期配置によってゲームの結果がどのように変わるのかに興味がある. しかしいきなり 2 次元の盤面で考えるのは難しいので,ひとまずは 1 次元の盤面で考えることにした. すなわち,この問題では盤面は縦幅 1,横幅無限のマス目であると見なす. また,オセロの駒はアルファベット小文字の ox によって表すことにする.

B君はこの盤面上のオセロの初期配置として N 個の駒を連続させて並べ,左から i 番目の駒を ci ∈ {o, x} とするものを考えることにした. 先手の駒を o とするとき,両方のプレイヤーが最善を尽くした時に勝利者がどちらになるかを求めて欲しい.

入力形式

入力は以下の形式で与えられる.

c1c2...cN

ci は初期配置における左から i 番目の駒を表す.

出力形式

勝利者の駒を出力せよ.なお,このゲームは引き分けにはならないことが保証されている.

制約

  • 入力の文字列の長さを N として,1 ≤ N ≤ 50 である.
  • ci ∈ {o, x}

入出力例

入力例 1

oxxoxoo

出力例 1

o

最初は o の番であるが,打てるマスが存在しないのでパスをする. 続いて x の番になり,左端と右端のどちらかに打つことができる.しかし,x がどちらに打ったとしても o に勝つことはできない.

入力例 2

xxxooxxox

出力例 2

x

Writer: 楠本充,小浜翔太郎
Tester: 田村和範

Source: Kyoto University Programming Contest 2012 , Kyoto, Japan, 2012-07-01
http://www.kupc.jp/
http://kupc2012.contest.atcoder.jp/