ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Задачи со всего света > задача:


Ездец

Задачи сборника

• Бронзовый призёр
• Вирусы
• День рождения Иванова
• Ездец
• Забавная игра
• Запаковка
• Максимум из минимумов
• Площадь пересечения
• Последовательность
• Почтовые цифры
• Прямоугольники
• Радиовышки

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Сложность Гамма

В 2010 году, когда старое здание лицея, наконец, отремонтировали, вместо школьной столовой в лицее открылось кафе "Колобок" с автоматическим и абсолютно бесплатным обслуживанием школьников. Кафе было круглое, в центре располагалась весьма аппетитная статуя Колобка, а вдоль стены на одинаковом расстоянии друг от друга стояли столики. Вкусная еда, приятный полумрак, цветы на столиках: Неудивительно, что лицеисты любили проводить там свое время.
Когда лицеист заходил в кафе, он выбирал себе свободный столик, садился за него, и с помощью специального пульта, расположенного над столиком, делал заказ. Заказы исполнялись специальным устройством, которое лицеисты прозвали "ездец". Ездец представлял собой простейшего робота, который умел перемещаться вдоль стены. Он подъезжал к нужному столику и выдавал заказанное. Естественно, что на это уходило какое-то время. Директор лицея заинтересовался эффективностью такого обслуживания. Его волновал вопрос: не слишком ли долго просиживают лицеисты за пустыми столиками в ожидании еды. Он обратились к лучшим программистам лицея с просьбой написать программу, вычисляющую среднее время выполнения заказа:
"История Лицея", Москва, Мир, 2040 г.

Постановка задачи
Вам дан список заказов: время, когда заказ поступил, и номер столика, с которого он сделан (столики пронумерованы по часовой стрелке от 1 до N).

Ездец устроен следующим образом:
Вначале он находится напротив столика номер 1 в состоянии "свободен". Когда поступает заказ, ездец переходит в состояние "обслуживание заказа". Он выбирает кратчайший из двух путей (по часовой или против часовой стрелки) от своего текущего положения до столика, который надо обслужить. На то, чтобы переместиться к соседнему столику, ездец тратит T1 секунд. (Таким образом, если, например, ему надо переместиться от 1-го столика к 5-му по часовой стрелке, то это займет 4*T1 секунд). Подъехав к нужному столику, он тратит еще T2 секунд на выдачу заказа. Затем он снова переходит в состояние "свободен" и остается у только что обслуженного столика.
Если какой-то заказ поступает в момент, когда ездец уже обслуживает другой заказ, то вновь поступивший заказ помещается в очередь и будет обслужен, как только ездец освободится. Если за время обслуживания заказа накопится несколько вновь поступивших заказов, то они будут выполняться в порядке очередности их поступления. Никакие два заказа не поступали одновременно.

Время ожидания (удовлетворения) заказа - это время между его поступлением и временем завершения его обслуживания. Среднее время ожидания - это сумма времен ожидания для всех заказов, деленная на количество заказов.

Ввод
На входе задано число N - количество столиков (1 < N < 1000), затем числа T1 и T2 (каждое из этих чисел - целое от 1 до 100). Затем идет число M - количество заказов (1 < M < 10000), и, наконец, M пар чисел целых чисел - время поступления и номер столика очередного заказа. Время поступления заказа указано в секундах, оно положительно и не превышает 30000. Заказы указаны в порядке их поступления (т.е. в порядке возрастания времени заказа).
Вывод
Вы должны вывести только одно число - среднее время ожидания заказа с тремя цифрами после десятичной точки.

Ввод Вывод
10
2 11
6
10 1
21 1
22 7
23 2
200 2
201 1
22.333

Для отправки решений необходимо выполнить вход.

www.contester.ru