|
Лимит времени 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
|
Для отправки решений необходимо выполнить вход.
|