← 返回题目列表

AtCoder · joisc2017_g

G. 长途客车

中文机器翻译题面 查看原题

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

長距離バス (Long Distance Coach) - 原题 PDF 第 1 页
原题PDF第1页
長距離バス (Long Distance Coach) - 原题 PDF 第 2 页
原题PDF第2页
長距離バス (Long Distance Coach) - 原题 PDF 第 3 页
原题PDF第3页
長距離バス (Long Distance Coach) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                              Contest Day 3 – Long Distance Coach


             長距離バス(Long Distance Coach)



  IOI 国には都市I と都市O を結ぶ長距離バスが走っている.バスの車内には給水器が設置されており,乗
客や運転手は水を飲むことができる.バスは時刻0 に都市I を出発し,時刻X に都市O に到着する.途中
には,水を補給できる地点がN 個ある.バスがi 番目(1 ≦i ≦N) の補給地点を訪れる時刻はS i である.
 最初,給水器には水は入っていない.バスの出発前に水を補給することができる.また,補給地点にお
いても水を補給することができる.水を補給するコストは,場所によらず,1 リットルあたりW 円である.
 このバスには都市I でM 人の乗客が乗車し,乗客には1 からM の番号が付けられている.都市I 以外
の場所では,新たな乗客が乗車することはない.乗客j (1 ≦j ≦M) は時刻D j に1 リットルの水を必要と
する.また,水を必要としてから時間T が経過する度に,再び1 リットルの水を必要とする.すなわち,
乗客j が水を必要とするのは,時刻D j + kT (k = 0, 1, 2, . . .) においてである.ここで,1 ≦D j < T であり,
T の値は乗客によらず一定である.乗客が水を必要としたときに給水器に水が残っていないと,その乗客
は途中下車してしまう.乗客j が都市O に到着する前に途中下車した場合,運賃の払い戻しとしてC j 円
のコストがかかる.
 運転手も水を必要とする.運転手は時刻0 に1 リットルの水を必要とし,乗客と同様,水を必要として
から時間T が経過する度に,再び1 リットルの水を必要とする.すなわち,運転手が水を必要とするのは,
時刻kT (k = 0, 1, 2, . . .) においてである.運転手が水を必要としたときに給水器に水が残っていないと,バ
スの運行を続けることができない.
  2 人以上の人が同時に水を必要とすることはない.また,バスが都市O や補給地点を訪れると同時に,
乗客や運転手が水を必要とすることはない.
 補給地点における水の補給量を調整することで,水の補給にかかるコストと,運賃の払い戻しにかかる
コストの合計を小さくして,バスを都市O まで運行したい.あなたの仕事は,バスの運行中に,どの地点
でどれだけ水を補給するかを決定することである.


課題

 バスの運行にかかる時間,補給地点の情報,乗客および運転手の情報が与えられたとき,バスを都市O
まで運行するための,水の補給にかかるコストと,運賃の払い戻しにかかるコストの合計の最小値を求め
るプログラムを作成せよ.


入力

 標準入力から以下のデータを読み込め.

   • 1 行目には,5 個の整数X, N, M, W, T が空白を区切りとして書かれている.これは,バスが時刻X に
   都市O に到着し,補給地点がN 個あり,バスに乗客がM 人いて,水1 リットルの補給にかかるコ
   ストがW 円であって,乗客や運転手が水を必要とする間隔がT であることを表す.




                     長距離バス– 1 / 4

The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                              Contest Day 3 – Long Distance Coach


   • 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数S i が書かれている.これは,バスがi 番目の補給地
   点を訪れるのが時刻S i であることを表す.

   • 続くM 行のうちのj 行目(1 ≦j ≦M) には,2 個の整数D j,C j が空白を区切りとして書かれている.
   これは,乗客j が最初に水を必要とする時刻がD j であることと,乗客j が途中下車した場合のコス
   トがC j 円であることを表す.


出力

 標準出力に,必要なコストの合計の最小値を表す整数を1 行で出力せよ.


制限

 すべての入力データは以下の条件を満たす.

   • 1 ≦X ≦1 000 000 000 000.

   • 1 ≦N ≦200 000.

   • 1 ≦M ≦200 000.

   • 1 ≦W ≦1 000 000.

   • 1 ≦T ≦X.

   • 1 ≦S i < X (1 ≦i ≦N).

   • 1 ≦Dj < T (1 ≦j ≦M).

   • 1 ≦C j ≦1 000 000 000 (1 ≦j ≦M).

   • D j (1 ≦j ≦M) は互いに異なる.

   • バスが都市O や補給地点を訪れると同時に乗客や運転手が水を必要とすることはない.


小課題

 この課題では小課題は全部で4 個ある.各小課題の配点および追加の制限は以下の通りである.

小課題1 [16 点]

   • N ≦8.

   • M ≦8.



                     長距離バス– 2 / 4

The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                              Contest Day 3 – Long Distance Coach


小課題2 [30 点]

   • N ≦100.

   • M ≦100.


小課題3 [25 点]

   • N ≦2 000.

   • M ≦2 000.


小課題4 [29 点]

 追加の制限はない.


入出力例

  入力例1        出力例1
   19 1 4 8 7           103
   10
   1 20
   2 10
   4 5
   6 5

 この入力例において,出発前に7 リットル,1 番目の補給地点で4 リットルの水を補給する場合,バス
の運行は次のように行われる.

   1. バスが都市I を出発する.この時点で給水器には7 リットルの水が入っている.

   2. 運転手および乗客1, 2, 3, 4 がそれぞれ時刻0, 1, 2, 4, 6 に水を1 リットルずつ飲み,残りの水量は2
   リットルになる.

   3. 運転手および乗客1 がそれぞれ時刻7, 8 に再び水を1 リットルずつ飲み,残りの水量は0 リットル
   になる.

   4. 時刻9 に乗客2 が水を必要とするが,給水器に水が無いので途中下車する.

   5. 時刻10 に1 番目の補給地点で水を4 リットル補給する.残りの水量は4 リットルになる.

   6. 乗客3, 4,運転手,および乗客1 がそれぞれ時刻11, 13, 14, 15 に水を1 リットルずつ飲み,残りの水
   量は0 リットルになる.

   7. 時刻18 に乗客3 が水を必要とするが,給水器に水が無いので途中下車する.



                     長距離バス– 3 / 4

The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                              Contest Day 3 – Long Distance Coach



   8. 時刻19 にバスが都市O に到着する.

 水の補給は計11 リットル行われるため給水にかかるコストは88 円である.乗客2, 3 が途中下車するコ
ストは合計で15 円である.これらの合計は103 円である
  102 円以下の合計コストでバスを最後まで運行することはできないので,103 を出力する.



  入力例2        出力例2
   105 3 5 9 10         547
   59
   68
   71
   4 71
   6 32
   7 29
   3 62
   2 35


  入力例3               出力例3
   1000000000000 1 1 1000000 6      333333209997456789
   999999259244
   1 123456789





                     長距離バス– 4 / 4