C - Cutting Swiss Roll

C - Cutting Swiss Roll 解説

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

白うさと黒うさはクリスマスケーキとして長さ N cm のロールケーキを購入した．このロールケーキは場所によって甘さが異なり，各 i (1 \leq i \leq N) に対し，ケーキの左端から i-1 cm の場所から i cm の場所までの甘さは整数 A_i で表される．

白うさと黒うさは，このケーキのうちちょうど 1 cm を 2 羽で一緒に食べ，残りの部分は冷蔵庫にしまおうと考えている．ケーキのどの部分を食べるかは以下のようにして決める．

まず白うさが，左端から k cm のところでケーキを 2 つに切り分ける．ここで k は 1 以上かつケーキの長さ未満の整数であればなんでもよい．
切り分けられた 2 つのケーキのうち，黒うさが好きな方をひとつを選んで冷蔵庫にしまう．

この手順 1, 2 を終えたあとでケーキがまだ 2 cm 以上残っている場合，次は黒うさがケーキを切り分けて白うさが片方を冷蔵庫にしまう．こうして長さ 1 cm のケーキが残るまで，白うさと黒うさは交代しながら手順 1, 2 を繰り返し行う．

白うさはとにかく甘いケーキが好きなので，最終的に残るケーキの甘さが最大になるように行動したいと考えている．一方，黒うさはビターな味付けのほうが好きなので，最終的に残るケーキの甘さが最小になるように行動したいと考えている．

双方が最適な行動をとったとき，最終的に残るケーキの甘さを X とする．白うさの最適な行動，すなわち黒うさがどのように行動しても最終的に甘さ X 以上のケーキを必ず残せるような戦略を実装したプログラムを作成せよ (X は明示的に与えられないことに注意せよ)．

あなたのプログラムが以下に示す入出力のフォーマットに従った上で，最終的に残ったケーキの甘さが X 以上である場合，正答と見なされる．

すべてのテストケースに正答すれば 100 点が与えられる．

まず，ケーキの長さを表す整数 N が標準入力に与えられる．続いて，ケーキの甘さを表す N 個の整数 A_1, A_2, ..., A_N が順に標準入力に与えられる．

その後，ケーキの切り分けが開始され，以下の入出力 1〜4 が繰り返される．

あなたのプログラムは，白うさがケーキを切る場所を表す整数 k を標準出力に出力する．これはケーキの左端から k cm の地点を切ることを意味する．
- k は 1 以上かつ現在のケーキの長さ未満でなければならない．
文字 L または R が標準入力に与えられる．L, R はそれぞれ黒うさが切れ目より左・右の部分を冷蔵庫にしまったことを表す．
- 黒うさのこの行動により残ったケーキが 1 cm になった場合，以降入力は与えられず，あなたのプログラムも直ちに終了せねばならない．
黒うさがケーキを切る場所を表す整数 k' が標準入力に与えられる．これはケーキの左端から k' cm の地点を切ることを意味する．
- k' は 1 以上かつ現在のケーキの長さ未満である．
あなたのプログラムは，文字 L または R を標準出力に出力する．L, R はそれぞれ白うさが切れ目より左・右の部分を冷蔵庫にしまうことを表す．
- 白うさのこの行動により残ったケーキが 1 cm になった場合，以降入力は与えられず，あなたのプログラムも直ちに終了せねばならない．

入出力例も参考にせよ．

ケーキの長さが 1 cm になった後，あなたのプログラムは直ちに終了しなければならない． 終了しなかった場合のジャッジ結果は不定である．また，正しくない出力をした場合の結果も不定である（必ずしも WA になるとは限らない）．

出力した後に，出力をflushしなければならないことに注意せよ．flushしなかった場合，TLEとなることがある．

各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径) を参考にするとよい．

N=5,\ A = \{1,2,3,4,5\} ときの入出力例を示す．

入力	出力	説明
`5` `1` `2` `3` `4` `5`		ケーキの長さ `N` と甘さ `A` が与えられている．
	`4`	白うさがケーキを左から `4` cm の点で切る．
R		黒うさが右の部分を冷蔵庫にしまう．
`1`		黒うさがケーキを左から `1` cm の点で切る．
	L	白うさが左の部分を冷蔵庫にしまう．
	`2`	白うさがケーキを左から `2` cm の点で切る．
R		黒うさが右の部分を冷蔵庫にしまう．
`1`		黒うさがケーキを左から `1` cm の点で切る．
	L	白うさが左の部分を冷蔵庫にしまう．この時点でケーキが `1` cm となるので応答は終了する．

上記の応答例では最終的に甘さ 3 のケーキが残っている．このケースでは X = 3 (白うさと黒うさが双方ともに最適に行動したときに残るケーキの甘さが 3) であるため，上記の応答例は正答と見なされる．