Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2365. Мост
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 22/10/2017 | Заочный онлайн-тур отборочных командных соревнований школьников Челябинской области (H) |
Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Необходимо написать программу для автоматизации работы моста.
Мост может быть поднят или опущен за 60 секунд. В это время ни движение
автотранспорта, ни движение судов не выполняется.
Судно может ожидать прохода через мост не более 30 минут. Суда могут проходить
мост только по отдельности и выполняют это действие за 20 секунд. Мост может опущен,
только если нет судов, ожидающих прохода. Но при необходимости можно оставить мост поднятым,
чтобы дождаться прибытия следующего судна (см. пример ввода 2).
Необходимо минимизировать время, в течении которого мост будет недоступен
для движения автотранспорта.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 4000`) – количество
ожидаемых судов. Далее следует `N` строк, в каждой строке одно целое число
`T_i` (`60\ ≤\ T_i\ ≤\ 10^5`) – время прибытия `i`-го судно в секундах.
`T_i` упорядочены по возрастанию. Кроме того, между появлением судов проходит не менее 20 секунд
(`T_i\ +\ 20\ ≤\ T_i+1`).
Вывести одно целое число – минимальное время, в течении которого мост будет недоступен
для движения автотранспорта.
Пример ввода 1
2 100 200
Пример вывода 1
160
Пример ввода 2
3 100 200 2010
Пример вывода 2
250
Пример ввода 3
3 100 200 2100
Пример вывода 3
300
