Задача . 10. Максимальная безопасная скорость

Максимальная безопасная скорость

Что должна делать программа

Для дороги с несколькими участками требуется подобрать наибольшую целую начальную скорость, при которой автомобиль гарантированно успевает остановиться до препятствия в рамках заданной модели.

Такие расчёты иллюстрируют, как одну модель движения можно многократно запускать для подбора допустимого параметра.

Математическая модель торможения

Пусть при выбранной начальной скорости V:

x₀ = 0,    v₀ = V.

Если в начале n-й секунды автомобиль находится на i-м участке дороги, то:

v_n+1 = max(0, v_n − A_i),

x_n+1 = x_n + v_n+1.

Если автомобиль находится точно на границе двух участков, используется параметр следующего участка.

Скорость V считается безопасной, если автомобиль достигает состояния v = 0 при x < D. Если x ≥ D раньше остановки или на том же шаге, скорость считается небезопасной.

Входные данные

В первой строке вводятся три целых числа:

N D Vmax

• N — количество участков дороги;
• D — расстояние до препятствия;
• Vmax — наибольшая начальная скорость, которую разрешено рассматривать.

В следующих N строках вводятся по два целых числа:

L A

• L — длина очередного участка дороги;
• A — величина, на которую скорость уменьшается за одну секунду на этом участке.

Участки идут подряд, их суммарная длина не меньше D.

Выходные данные

Выведите одно целое число — максимальную безопасную начальную скорость V из диапазона от 1 до Vmax.

Если даже скорость 1 небезопасна, выведите 0.

2 100 60
50 5
50 8

38

2 70 50
30 2
40 6

24