実行時間制限: 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 は明示的に与えられないことに注意せよ).
制約
- 2 \leq N \leq 5,000.
- 1 \leq A_i \leq 10^9.
- A_i は整数.
採点
あなたのプログラムが以下に示す入出力のフォーマットに従った上で,最終的に残ったケーキの甘さが 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) であるため,上記の応答例は正答と見なされる.