Осмотр достопримечательностей
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Динамическое программирование
- Математика
Вы начинаете в городе 1 в момент времени 0 и едете по порядку через города 2, …, N, по автобусу между каждой соседней парой. Автобус из города i в город i+1 задан тройкой [S, F, D]: он отправляется в моменты S, S+F, S+2F, … и идёт D единиц времени. Посадка и высадка времени не занимают, ждать автобус можно сколько угодно.
В каждом из городов 1..N−1 (кроме последнего) можно потратить sight_time на осмотр, а можно сразу ждать автобус; дважды в одном городе осматривать нельзя. В город N нужно прибыть не позже момента deadline.
Параметры: sight_time, deadline и список buses из N−1 троек (N от 2 до 2000, значения до 10^9). Верните наибольшее число городов, которые можно осмотреть, или -1, если успеть в город N вовремя нельзя вообще.
Пример: 3, 12, [[3, 2, 1], [6, 2, 2], [1, 3, 2]] → 2.
Источник: Coding Competitions Archive, kickstart/2017/round_d/sightseeing · © Google LLC · Apache-2.0 · условие переведено и дополнено