TCO13 Round1A Div1 500

問題

ぴったりXの距離だけジャンプできるカエルがいる。
数直線上を原点からスタートして、距離D以上になるまでジャンプを繰り返す。
間に、L[i]からR[i]までの幅の穴がいくつか空いている。(L[i],R[i]の端点は穴に落ちない)
穴に落ちないようにする場合、最小のXを見つける。Xは小数かもしれないことに注意。

L[i],R[i],Dは整数
0<=L[i]

考え方

まず、穴の中で最大の幅のもの以上の距離をジャンプできないと落ちてしまうので、それを求めておく。

答えが小数になるので、穴に落ちない候補となるXは無数に存在してしまう。
しかし、最適解の候補は、何回かジャンプした後で、穴の両端に着地するような場合になるはず。

(一つの穴を考えて試してみると、穴の左端に到着する場合は、穴の右端に到着する場合の方が短くなるパターンが見つかるので、穴の右側だけでよい)

すべての最適解の候補を実際に試してみて、一番小さいものを見つける。

ただし、
・穴の端の数は、100(50)
・候補点数は、穴の端の数*30000ぐらい
・候補のジャンプ幅Xの最小値が1
とすると、距離D以上までいけるかどうかの判定に単純なシミュレーションをしてしまうと、
候補点数(100*30000)*幅1*30000step=9*10^10ぐらいでやばい。

ジャンプ幅Xが穴(L[i],R[i])に落ちるかどうかは、L[i]を超えるXの倍数を見つければよい。
floorなどを使ってそのようなXの倍数を(1,2回の計算で)求められるので、上記の判定は、穴の数=50回程度で判定できる。
100*30000*1*50=1.5*10^8にまで落ちる。
候補点数は実際はもっと小さくなるので、間に合う。無駄な計算を省くようにすればもっと減る。

反省

• 小数を扱うときはEPSは必ず考慮。<とか>だけでも。
• 二分探索かと思ったけど、それにこだわり続けず、ほかの方法も考える