Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1311. Веревочные мосты
Стеки, очередиОлимпиадные задачи на русском языке
| 15/12/2009 | Сборы, группа 2 (3) |
Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Эльфы для скрытного передвижения по лесу установили веревочные мосты, соединяющие последовательно несколько деревьев.
Каждый мост имеет максимальную прочность, которая ограничивает число эльфов, одновременно находящихся на нем.
Для быстрого перемещения большой группы эльфов по этим мостам, они придерживаются следующих правил:
- Если два или больше эльфа могут перейти по мосту, они двигаются по нему вместе группой, не превышающей ограничения по прочности моста, следуя шаг в шаг, чтобы предотвратить раскачивание моста. По той же причине на мосту в каждый момент времени может быть только одна группа (группа может состоять из одного эльфа).
- Как только мост освобождается, на него вступает следующая группа, ожидающая перехода через этот мост, не дожидаясь других эльфов, которые переходят предыдущий мост.
Напишите программу, которая вычисляет время перехода по указанным правилам для `P` эльфов по заданному набору мостов.
В первой строке ввода содержатся два целых числа `B` и `P` (`1\ ≤\ B,\ P\ ≤\ 20`) – количество мостов и количество эльфов.
В следующих `B` строках содержатся по два целых числа `C_i` и `T_i` (`1\ ≤\ C_i\ ≤\ 5`, `1\ ≤\ T_i\ ≤\ 100`) – ограничение
на количество эльфов на `i`-ом мосте и время перехода в секундах через `i`-й мост.
Вывести одно целое число – общее время перехода всех эльфов через последовательность мостов.
Пример ввода 1
1 8 3 25
Пример вывода 1
75
Пример ввода 2
4 8 1 8 4 30 2 10 1 12
Пример вывода 2
162
