Автомобиль «Пантера»

Переберем исходное время $$$t$$$. Можно заметить, что при любом $$$SpeedLimit$$$ оно будет порядка $$$O(d^{0.5})$$$.

Оптимальной стратегией движения автомобиля будет следующая: в начале мы ускоряемся, затем не меняем скорость, а в конце замедляемся. Найдём максимальное расстояние, которое можно проехать за время $$$t$$$. Заметим, что если мы смогли проехать расстояние $$$d_1 > d$$$, то $$$d$$$ мы тоже сможем проехать(достаточно уменьшать скорость на $$$1$$$ в каких-то точках, единственное ограничение — модуль разности скоростей в соседние моменты времени не должен быть больше $$$1$$$). В тупом решении можно просто симулировать за $$$O(t)$$$ , но можно и посчитать расстояние за $$$O(1)$$$: определим максимальную скорость $$$x$$$, до которой можно ускориться, чтобы потом успеть замедлиться до $$$0$$$; затем достаточно посчитать сумму от $$$1$$$ до $$$x$$$, умножить $$$x$$$ на время, которое мы будем двигаться с этой скоростью, и посчитать сумму от $$$x$$$ до $$$1$$$. Таким образом, получаем решение за $$$O(d^{0.5})$$$.

Для полного решения достаточно заметить, что $$$t$$$ можно перебирать с помощью бинарного поиска по ответу, так как значения функции «максимальное расстояние, которое можно проехать за время $$$x$$$» возрастают, и получить решение за $$$O(log d)$$$.

Также существует решение за $$$O(1)$$$: можно расписать формулу максимального пройденного расстояния за время $$$t$$$, и найти оптимальное $$$t$$$, решив квадратное уравнение.