以下是来自日本的原始新闻PDF,已完整保存和染色。



可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 4 – Apples
リンゴの出荷(Apples)
JOI 農場ではリンゴの入荷と出荷を行っている.JOI 農場は1 つずつリンゴを入荷し,出荷依頼が来た場
合は次の入荷を待たずに対応を行う.出荷依頼では出荷するリンゴの個数が指定されており,JOI 農場は
出荷依頼が来た時,出荷依頼で指定されている個数のリンゴを,JOI 農場の決まりを満たす組み合わせで
出荷できる場合,すぐにそれらのリンゴを出荷する.一方,出荷できない場合は,出荷できないことを伝
えリンゴは全く出荷しない.
今年はJOI 農場に多くのリンゴの入荷と多くの出荷依頼が来ることが見込まれている.そこで,あなた
にJOI 農場のためのリンゴ管理プログラムを書いて欲しい.
課題
各々のリンゴには色の濃さが整数値で決まっている.1 回の出荷におけるリンゴの濃さのバラつきとは,
出荷されるリンゴの濃さの最大値と最小値の差である.JOI 農場では各出荷依頼について,濃さのバラつ
きがB 以下でなければならない,という決まりがある.
JOI 農場が行うリンゴ管理プログラムへは合計M 個の要求が行われる.i 番目の要求は「リンゴの入荷」
「出荷依頼」「プログラムの終了」の3 種類のうちのいずれかである.それぞれの要求に対し,リンゴ管理
プログラムは以下の動作をしなければならない.
• 「リンゴの入荷」の要求に対しては,濃さの値がDi のリンゴを1 個入荷したことが入力されるので,
これを記憶する.
• 「出荷依頼」の要求に対しては,Ni 個のリンゴを出荷する出荷依頼が来たことが入力されるので,出
荷できる場合は出荷するリンゴの濃さの値をそれぞれ昇順に出力し,出荷できない場合はNO を出力
する.ただし,出荷するリンゴの組み合わせの候補が複数存在する場合は,リンゴの色の濃さの値の
総和が最も大きくなる組み合わせを選択する.
• 「プログラムの終了」の要求に対しては,リンゴ管理プログラムの終了命令が入力されるので,プロ
グラムを終了する.
注意
この課題は応答型課題(Reactive task) である.i 番目の要求が「出荷依頼」である場合,i + 1 番目の要求
の入力はi 番目の出荷依頼に対する出力をした後に与えられる.
また,出力がバッファされ,読み込みが誤ってブロックされてしまうことを防ぐ必要がある.そのため
読み込みを行う前にfflush(stdout); などを記述しておくことを勧める.
リンゴの出荷– 1 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 4 – Apples
制限
1 ≦M ≦100 000 プログラムに渡される要求の数
0 ≦B ≦1 000 000 000 各出荷毎のリンゴの濃さのバラつきの上限値
0 ≦Di ≦1 000 000 000 (1 ≦i ≦M) i 番目の要求で入荷するリンゴの色の濃さの値
1 ≦Ni ≦100 000 (1 ≦i ≦M) i 番目の要求で出荷するリンゴの個数
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数M, B が空白を区切りとして書かれており,要求の個数がM 個,JOI 農場の決まりで
ある,リンゴの濃さのバラつきの上限値がB であることを表す.
• 1 + i 行目(1 ≦i ≦M −1) には「リンゴの入荷」「出荷依頼」のどちらかの要求を示す情報が書かれて
いる.
– i 番目の要求が「リンゴの入荷」である場合,文字A と,入荷したリンゴの色の濃さの値を表す
整数Di が空白を区切りとして書かれている.
– i 番目の要求が「出荷依頼」である場合,文字R と,出荷依頼の依頼内容である出荷するリンゴ
の個数を表す整数Ni が空白を区切りとして書かれている.
• 1 + M 行目には「プログラムの終了」の要求を表す文字E のみが書かれている.
出力
各「出荷依頼」の要求を受けた時に,出荷できない場合は文字列NO を1 行で出力せよ.出荷できる場
合は,出荷するリンゴの色の濃さを昇順で空白を区切りとして1 行に出力せよ.
採点基準
採点用データのうち,配点の30%分については,B ≦10 000 かつDi ≦10 000 (1 ≦i ≦M) を満たす.
リンゴの出荷– 2 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 4 – Apples
入出力の例
入力例 出力例
22 10
A 5
A 16
R 2
NO
A 10
R 2
10 16
R 2
NO
A 15
A 5
R 2
5 15
A 5
R 2
5 5
A 0
A 10
R 1
10
A 10
A 10
R 4
NO
A 30
R 4
NO
A 0
R 4
0 0 10 10
E
リンゴの出荷– 3 / 3