시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 50 | 37 | 34 | 73.913% |
国際情報オリンピック日本大会の競技会場の近くにはトイレが 2 つある.片方は女性専用トイレで,も う片方は男女共用トイレである.女性はどちらのトイレも利用できるが,男性は男女共用トイレのみ利用 できる.
競技が終了したので,2N 人の選手がトイレを利用するために一列に並んだ.並んだ選手はいずれも男性 または女性のどちらかである.選手は次の規則に従い,順番にトイレを利用する.
すべての選手はトイレに入ってから出るまでに 1 分かかる.選手がトイレに向かうのにかかる時間は無 視してよい.
列をあらかじめ並べ替えることで,N 分後の時点で全員がトイレの利用を終えているようにしたい.
列の並べ替え方に対して,選手の不満度を次のように定義する.
不満度の定義において,実際にトイレに入るときに発生する順番の入れ替えは考慮しない.
N 分後の時点で全員がトイレの利用を終えているような列の並べ替えをうまく定めることで,選手の不 満度の最大値をできるだけ小さくしたい.
トイレに並んでいる 2N 人の選手に関する情報が与えられたとき,N 分後の時点で全員がトイレの利用 を終えているように列を並べ替えることができるかを判定し,できる場合は,選手の不満度の最大値とし て考えられる値のうち,最小の値を求めるプログラムを作成せよ.
標準入力から以下のデータを読み込め.
これらのデータから,選手の列を表現する長さ 2N の文字列 X を次のように定める.
この文字が ‘M’ のときは男性であることを表し,‘F’ のときは女性であることを表す.
標準出力に,選手の不満度の最大値として考えられる値のうちの,最小の値を 1 行で出力せよ.ただし, どのように列を並べ替えても N 分後に全員がトイレの利用を終えることが不可能な場合は,-1 を出力せよ.
追加の制限はない.
6 1 FFFMMMMMMFFF 1
2
入力例 1 では 12 人の選手が一列に並んでいる.次のように列を並べ替える.
この並べ替え方において,選手の不満度の最大値は 2 である.並べ替えた後,選手の列を表す文字列は FMMFFMMMMFFF となる (‘M’ は男性を,‘F’ は女性を表す).並べ替えた後の列において,前から i 番目 (1 ≦ i ≦ 12) の選手を選手 i とする.選手は次のようにトイレを利用する.
選手の不満度の最大値が 2 より小さくなる並べ替え方は存在しないので,2 を出力する.
6 1 MMFFMMMMFFMF 1
-1
6 1 MFFFMFMMFFFM 1
0
6 4 M 1 F 2 FM 2 MFFFM 1
0