Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Лифты (30 баллов)

Автор задачи: Ефимов А.Е.

Задачу добавил: alef

Успешно сдано решений: 5

Наконец, NN приехал в город ММ, и теперь ему предстоит поселиться на время семинара в общежитии УУУ. В этом общежитии есть N лифтов из которых M даже работают (лестницы в архитектуре здания не предусмотрены). Каждый лифт вмещает до К человек, но когда он приезжает, войти в него успевает только 1 человек, поскольку после этого лифт мгновенно закрывает свои двери (выйти успевают все желающие).
Известна скорость движения лифта (E этажей в час, для всех лифтов она одинакова), а также количество людей на каждом этаже в начальный момент времени и то, на какой этаж они хотят приехать. Определить, сколько времени пройдет, прежде чем все они попадут на нужный им этаж.
Известно расположение лифтов на этажах в начальный момент времени. Все они сначала начинают двигаться вверх, при движении останавливаются на каждом этаже. Когда лифты достигают последнего этажа, они начинают двигаться вниз, а когда достигают первого этажа - начинают двигаться вверх.

Формат входного файла input.txt
Первая строка - четыре целых числа: M (1<=M<=20) - количество работающих лифтов, E  (1<=E<=1000) - скорость лифта, измеренная в этажах в час, K (1<=K<=10) - максимальное количество человек, которое вмещает лифт, и H (1<=H<=20) - количество этажей в здании.
Вторая строка - M целых чисел через пробел, каждое из которых отвечает номеру этажа, на котором в начальный момент времени расположен каждый из М лифтов.
Каждая из последующих H строк содержит номер этажа, на который хотят попасть ожидающие лифт люди, находящиеся на данном этаже, и их количество Q (0<=Q<=15) (третья строка во входном файле содержит номер этажа, на который хотят попасть люди, находящиеся на первом этаже, и их количество, четвертая - на втором и т.д.)

Формат выходного файла output.txt
Время, которое требуется, чтобы все попали на нужный этаж, в формате <часы>:<минуты>

Пример входного файла

2 3 4 5
1 2
4 1
5 1
1 1
5 1
4 1


Пример выходного файла

02:20

Сдать задачу

Задать вопрос жюри по этой задаче