ioi2011 logo

International Olympiad in Informatics 2011
2011年7月22-29日, タイ, パタヤ
Day 1 競技課題
日本語版

RICEHUB

バージョン: 1.4

米集積所 (Rice Hub)

田園地方に「米の道 (Rice Way)」として知られるまっすぐな道がある. この道に沿って R ヶ所の水田がある. 各水田は 1 以上 L 以下の整数座標に位置する. これら R ヶ所の水田は座標の非減少列で表現される. 形式的に書くと, 0 ≦ i < R なる任意の i に対して, 水田 i は座標 X[i] に位置する. 1 ≦ X[0] ≦ ... ≦ X[R−1] ≦ L と仮定して良い.

複数の水田が同じ座標となる場合があることに注意せよ.

収穫した米をなるべく多く貯蔵するために米集積所を1ヶ所建設する計画がある. 水田と同様に, 米集積所は 1 以上 L 以下の整数座標に位置しなければならない. 水田が１つ, あるいは, ２つ以上存在する座標を含めて, 1 以上 L 以下の整数座標であればどこにでも米集積所を建設できる.

各水田は収穫期ごとにちょうどトラック1台分の米の収穫がある. 集積所に米を輸送するため, 市はトラック運転手を雇わなければならない. トラック1台分の米を集積所に輸送するのに運転手に支払う賃金は1単位距離あたり1バーツである. つまり, トラック1台分の米をある水田から米集積所に輸送するコストはそれらの座標の差に等しい.

残念なことに, 今期の予算は厳しく, 輸送に高々 B バーツしか支払えない. あなたの課題は, なるべく多くの米を集められるように米集積所の位置を決めるのを助けることである.

課題 (Your task)

次のパラメータを持つプロシージャー besthub(R, L, X, B) を実装せよ:

あなたが実装するプロシージャーは集積所の最適な位置を探し, 予算内で集積所に輸送できる米は最大でトラック何台分かを返せ.

米の総輸送費は非常に大きくなることがあることに注意せよ. 予算は 64-bit 整数で与えられる. 解答では 64-bit 整数を使用することを勧める. C/C++ では long long 型を使用し, Pascal では Int64 型を使用せよ.

例 (Example)

例として, R ＝ 5, L ＝ 20, B ＝ 6,

1
2
X＝10
12
14

の場合を考える.

この場合は, 集積所の最適な位置は複数存在し, 10 以上 14 以下のどの位置に建設してもよい. 上の図はこれらの最適な位置の１つを示しており, 座標 10, 12, 14 の水田から米を輸送することができる. どの最適な位置に対しても, 総輸送費は 6 バーツを超えない. 明らかに, ３ヶ所より多くの水田から米を集められる集積所の位置は存在しない. よって, この解は最適であり, besthub は 3 を返さなければならない.

小課題 (Subtasks)

小課題 1 (17 点)

  • 1 ≦ R ≦ 100
  • 1 ≦ L ≦ 100
  • 0 ≦ B ≦ 10 000
  • (この小課題に限っては)どの２つの水田も
    同じ座標ではない.

小課題 3 (26 点)

  • 1 ≦ R ≦ 5 000
  • 1 ≦ L ≦ 1 000 000
  • 0 ≦ B ≦ 2 000 000 000

小課題 2 (25 点)

  • 1 ≦ R ≦ 500
  • 1 ≦ L ≦ 10 000
  • 0 ≦ B ≦ 1 000 000

小課題 4 (32 点)

  • 1 ≦ R ≦ 100 000
  • 1 ≦ L ≦ 1 000 000 000
  • 0 ≦ B ≦ 2 000 000 000 000 000

実装の詳細 (Implementation details)

制限 (Limits)

インターフェース (API) (Interface (API))