空の文字列に対し、2人のプレイヤーが以下の操作を行います。
0
と1
のどちらかを選び、の末尾に付け加える。0
と1
のどちらかを選び、の末尾に付け加える。このようにしてできたを2進数として解釈した値をとするとき、
とします。
長さの文字列に対し、において以下の条件が満たされているものとします。
T[k]='0'
の時、である。T[k]='1'
の時、である。T[k]='?'
の時、の値は不明である。両方のプレイヤーが最善をつくした時、勝つのはどちらになるか、あるいは与えられた情報だけでは判断できないかを答えてください。
'0'
,'1'
,'?'
のいずれか入力は以下の形式で与えられます。
n T
先手が勝つならFirst
, 後手が勝つならSecond
, 与えられた情報だけでは判断できないならばUnknown
を出力して下さい。
2 1101
First
先手が0
を選べば、後手が0
, 1
のいずれを選んでも先手の勝利になります。
2 ????
Unknown
に関する情報が何もないので、勝敗を特定できません。
2 10?0
Second
先手が0
,1
のいずれを選んでも、後手が0
を選べば後手の勝利になります。
の値が不明ながあっても、勝敗が確定するケースがあることに注意して下さい。