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


可复制的 PDF 提取文本
5 ダンジョン
問題
あなたはあるダンジョンの地下N 階にある財宝を手に入れたいと思っている.最
初,あなたは地下1 階におり,あなたの体力はH(H は正整数) である.下の階に降
りるときに,体力が消費される.あらかじめ各階における下の階に降りるときに消
費される体力が分かっている.一方,各階には1 つの回復の泉があり,泉を1 回使う
ごとに回復できる体力がそれぞれ定まっている.体力が0 以下になるとあなたは死
んでしまう.また,体力がH よりも高くなることはない.回復の泉は何回でも使う
ことができるが,回復には時間がかかるので,あなたは泉の使用回数をできるだけ
少なくしたいと考えている.
N,H,各階の下の階に降りるときに消費される体力,そして各階で回復の泉を1
回使用したときに回復する体力が与えられたとき,体力を0 以下にすることなく地
下N 階まで到達するために必要な泉の使用回数の最小値を求めるプログラムを作成
せよ.
また,一度下の階に降りると,財宝を手に入れるまで上の階に戻ることはできない.
入力
入力ファイルのファイル名はinput.txt である.
入力はN 行からなる.入力の1行目には2つの整数N, H(2 ≦N ≦100000 = 105, 1 ≦
H ≦10000000 = 107) が空白を区切りとして書かれている.N は地下N 階に財宝が
あるということを表し,H は初期体力( ダンジョンの地下1 階に到着した段階の体
力) であり,かつ体力の最大値である( 回復によって体力がH より大きくなること
はない) .
続くN −1 行には,2 つの整数が空白を区切りとして書かれている.1 + i 行目
(1 ≦i ≦N −1) の整数di ,hi について,di は地下i 階から地下i + 1 階に降りる際
に消費される体力を,hi は地下i 階で泉を1 回使用したときに回復する体力を表す
(0 ≦di < H, 1 ≦hi < H).
どの採点用データにおいても,地下N 階にたどり着く方法が存在する.採点用デー
タのうち,配点の10%分については,N ≦1000 かつH ≦1000 を満たす.配点の
30%分については,N ≦1000 を満たす.配点の50%分については,泉の使用回数の
最小値が106 を超えない.
問題5-1
出力
出力ファイルのファイル名はoutput.txt である.
output.txt は,体力を0 以下にすることなく地下N 階に到達するために必要な,
泉の使用回数の最小値を含む1 行からなる.
注意
この問題では,扱う整数の範囲が32bit に収まらない可能性があることに注意せよ.
入出力の例
input.txt
10 10
4 2
2 5
6 1
7 3
6 4
9 6
0 8
4 1
9 4
output.txt
10
問題5-2