Категория: Паскаль

Олимпиадная задача по информатике (программированию).

В 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

Программа написана на Pascal (Delphi). Исходный код в 'Prog.dpr'. Ввод-вывод консольный (с клавиатуры).