Задача 19: Ездец (II открытая Кировская
командная олимпиада)
В 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. Заказы указаны в порядке их
поступления (т.е. в порядке возрастания времени заказа).
Выходные данные
В выходной файл вы должны поместить только одно число - среднее
время ожидания заказа с тремя знаками после запятой.
Примеры входного и выходного файлов
D.IN
10
2 11
6
10 1
21 1
22 7
23 2
200 2
201 1
D.OUT
22.333
Решение:
Вообще-то достаточно простая задача. Будем считывать заказы по
одному. У нас будет переменная, указывающая на настоящий момент
времени, первоначально приравняем ее к нулю. Если время поступления
заказа больше чем настоящий момент, то присваиваем настоящему
моменту время поступления заказа (у робота не разработана система
предсказания заказов). Если же настоящий момент больше времени
заказа, то прибавляем к общему времени ожидания разность, между
настоящим моментом и временем заказа (робот обслуживал не нас).
Теперь будем определять время, затраченное на собственно наше
обслуживание. Сначала нам необходимо определить - какое расстояние
меньше - по часовой или против часовой стрелки. Это уместно вынести
в отдельную функцию, которая будет выбирать минимум между abs(a - b)
[едем, не проезжая через первый столик] и ((n - a + b) mod n)
[проезжаем мимо первого и последнего столиков]. Прибавим к
настоящему моменту и времени ожидания минимум, умноженный на t1.
Теперь просто добавим к времени ожидания и настоящему моменту t2.
Осталось только вывести результат: (время ожидания) / m
Далее
ð
