No.1139 Slime Race
タグ : / 解いたユーザー数 318
作問者 :
eSeF
/ テスター :
nok0
問題文
無限に続く数直線上でスライムのレースが行われていて、$N$ 匹のスライムが参加しています。
$i$ 番目のスライムは時刻 $0$ に座標 $x_i$ に居て、
正の方向に一定の速さ $v_i$ で進んでいます。
レースは１本の直線上で行われているので、
レース中にスライムたちが衝突することがあります。
ある時刻 $t$ に複数のスライムが同一の座標にいる状態になったとき、
それらのスライムは以下のように変化します。
・番号の一番小さいスライムがその他のスライムを全て吸収し、吸収されたスライムは消滅する。
番号の一番小さいスライムは、速さが
（自分の吸収前の速さ）＋（自分が吸収したスライムの速さの和）
に変化する。
さて、全てのスライムについて時刻 $0$ から時刻 $t$ までに走った距離を求め、
それらを足し合わせた総和を $f(t)$ と表します。
$f(T)\ge D$ である最小の整数 $T$ を求めてください。
なお、吸収され消滅したスライムは、その時点で走るのを終了したとみなして下さい。
入力
$N\ \ D$ $x_1\ \cdots \ x_N$ $v_1\ \cdots \ v_N$
【制約】
・$1\le N\le 10^5$
・$1\le D\le 10^9$
・$1\le x_i\le 10^9$
・$1\le v_i\le 10^9$
・$i< j$ ならば $x_i < x_j$
・入力は全て整数である。
出力
問題文の条件を満たす整数 $T$ を出力せよ。
サンプル
サンプル1
入力
3 40 2 5 100 6 4 5
出力
3
$t=\dfrac{3}{2}$ にスライム１と２が座標 11 で衝突します。
このとき、スライム２は消滅し、スライム１の速さは $6+4=10$ になります。
$f(\frac{8}{3})=\{ 6\times \frac{3}{2}+10\times (\frac{8}{3}-\frac{3}{2}) \}+\{4\times \frac{3}{2} \}+\{5\times \frac{8}{3}\}=40$
、$2< \dfrac{8}{3} < 3$ であるので、$f(T)\ge 40$ となる最小の整数は $3$ です。
サンプル2
入力
3 9 1 3 7 1 1 1
出力
3
衝突が起きない場合もあります。
サンプル3
入力
1 160 314 159
出力
2
スライムが１匹ですが、これもレースと呼びます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。