以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。




可复制的 PDF 提取文本
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Spring Training Camp/Qualifying Trial
March 19–25, 2017 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Sparklers
手持ち花火(Sparklers)
JOI 君は自分を含めてN 人の友だちと一緒に手持ち花火で遊ぶことにした.今回使う手持ち花火は,点
火してからちょうどT 秒間だけ燃え続ける.
最初,JOI 君たちは東西に一直線に伸びた道の上に,1 人につき1 本手持ち花火を持った状態で散らばっ
て立っている.JOI 君たちには,それぞれ,1 以上N 以下の番号が1 つずつ振られている.ただし,i < j
ならば,i 番の人はj 番の人よりも西に立っているか,または,i 番の人はj 番の人と同じ場所に立っている
とする.i 番の人は最も西に立っている人(1 番の人) からXi メートル東に進んだところに立っている.JOI
君はK 番の人である.
花火で遊び始めようとしたとき,着火するためのライターの燃料の残りが少なく,1 本の花火に着火す
ることしかできないことに気がついた.
そこでJOI 君たちは,まずJOI 君の花火にライターで着火し,その後,花火から花火へと火を移してい
くことで他の友だちの花火にも着火することにした.
花火はT 秒間しか燃え続けないので,JOI 君たちは協力して火を移していかなければならない.花火か
ら花火に火を移すためには,以下の条件を満たさなければならない.
• 火を移す方の花火は,着火後T 秒以内の状態でなければならない.着火後ちょうどT 秒経過した状
態でもよい.
• 火を移される方の花火は,まだ着火されたことがない花火でなければならない.
• 火を移す方の花火を持っている人と,火を移される方の花火を持っている人は,同じ地点に立ってい
なければならない.
花火の火を移すのにかかる時間は無視できるものとする.
初めJOI 君たちは散らばって立っているので,火を移すためにはうまく移動しないといけない.JOI 君た
ちは,それぞれ,好きな速度で東西の好きな向きに走ることができる.しかし,遊んでいる最中にあまり
速く走るのは危険なので,JOI 君たちは1 秒あたりs メートル以下の速度で走らなければいけないという
速度制限を設けることにした.ここで,s は0 以上の整数である.
全ての花火に火を移すためには,速度制限を1 秒あたり何メートルに設定すればよいだろうか.
課題
花火が燃え続ける時間とJOI 君たちの最初の位置が与えられたとき,全ての花火に火を移すことが出来
るような速度制限であって整数であるものの最小値s を求めるプログラムを作成せよ.
手持ち花火– 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 1 – Sparklers
入力
標準入力から以下のデータを読み込め.
• 1 行目には整数N, K, T が空白を区切りとして書かれている.これは,JOI 君たちの人数がN 人であ
り,JOI 君がK 番の人であり,花火は火をつけてからちょうどT 秒間だけ燃え続けることを表す.
• 続くN 行のうちのi 行目(1 ≦i ≦N)には,整数Xi が書かれている.これは,最初,最も西に立っ
ている人から東にXi メートル進んだところにi 番の人が立っていることを表す.
出力
標準出力に,全ての花火に火を移すことが出来るような速度制限であって整数であるものの最小値s を
1 行で出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 1 ≦K ≦N ≦100 000.
• 1 ≦T ≦1 000 000 000.
• 0 ≦Xi ≦1 000 000 000 (1 ≦i ≦N).
• X1 = 0.
• Xi ≦X j (1 ≦i ≦j ≦N).
小課題
この課題では小課題は全部で3 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [30 点]
• N ≦20.
小課題2 [20 点]
• N ≦1 000.
小課題3 [50 点]
追加の制限はない.
手持ち花火– 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 1 – Sparklers
入出力例
入力例1 出力例1
3 2 50 2
0
200
300
この入力例では,速度制限を秒速2 メートルにすればよい.
まず,1 番の人が東向きに,2 番の人が西向きに,3 番の人が西向きにそれぞれ秒速2 メートルで進む.
50 秒後には2 番の人から1 番の人に火を移すことができる.
次に,1 番の人が東向きに,3 番の人が西向きにそれぞれ秒速2 メートルで進む.25 秒後には1 番の人
から3 番の人に火を移すことができる.
速度制限を秒速1 メートルにすると,全ての花火に火を移すことが出来ない.
入力例2 出力例2
3 2 10 8
0
200
300
この入力例では,速度制限を秒速8 メートルにすればよい.
まず,1 番の人が東向きに,2 番の人が東向きに,3 番の人が西向きにそれぞれ秒速8 メートルで進む.
2 番の人は3 秒後にその場に止まる.1 番の人と3 番の人はそのまま動き続ける.
さらに6.5 秒後に2 番の人と3 番の人が同じ位置に来るが,火は移さない.2, 3 番の人はその場に止ま
る.1 番の人はそのまま動き続ける.
さらに0.5 秒後に2 番の人から3 番の人に火を移す.1 番の人はそのまま動き続ける.3 番の人が西向き
に秒速8 メートルで進む.
さらに9 秒後に1 番の人と3 番の人が同じ位置に来る.3 番の人から1 番の人に火を移す.
速度制限を秒速7 メートルにすると,全ての花火に火を移すことが出来ない.
手持ち花火– 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 1 – Sparklers
入力例3 出力例3
20 6 1 6
0
2
13
27
35
46
63
74
80
88
100
101
109
110
119
138
139
154
172
192
手持ち花火– 4 / 4