Автобусный диспетчер

ЗАДАЧА 25. АВТОБУСНЫЙ ДИСПЕТЧЕР

Имя входного файла — bus.in

Имя выходного файла — bus.out

Ограничение времени — 3 секунды на тест

Ограничение памяти — 16 Мb

На кольцевом маршруте №54 протяженностью S, проходящем мимо пансионата «Энергетик», работает N

автобусов. Автобусы пронумерованы числами от 1 до N в порядке их следования по маршруту. Автобус с номером

1 движется за автобусом с номером N. Расписание составлено таким образом, что автобусы движутся с одинаковой

скоростью V 0 и с равными интервалами между ними. Движение автобусов контролирует диспетчер.

В 12 часов дня некоторые K автобусов одновременно снимаются с маршрута и отправляются на обед. Для

восстановления равенства интервалов между автобусами, продолжающими движение по маршруту, потребуется

некоторое время Т и, возможно, изменение скорости некоторых автобусов по команде диспетчера. В течение этого

времени автобусы должны двигаться с постоянными скоростями из интервала [V min , V max ], назначенными

диспетчером. Изменение скорости движения автобуса происходит мгновенно. По истечении времени Т автобусы

возобновляют движение по маршруту со скоростью V 0 .

Требуется написать программу для автоматического диспетчера, которая вычисляет минимальное время

T min , за которое интервалы движения между оставшимися автобусами станут равными, и скорости движения

каждого из них в течение этого времени.

Входные данные

Входной файл bus.in содержит две строки.

В первой строке находятся натуральные числа N, К, S, V min , V max и V 0 , где K <N  10000, S  10000,

V min < V max  10000, V min  V 0  V max .

Во второй строке расположены в порядке возрастания K чисел — номера автобусов, снятых с маршрута.

Все данные в строках разделены пробелами.

Выходные данные

В первой строке выходного файла bus.out должно находиться значение T min .

В каждой из последующих N – K строк должны быть по два разделенных пробелом числа — номер автобуса

на маршруте и скорость его движения в течение времени T min . Номера автобусов упорядочить по возрастанию.

Значения T min и скоростей выводить с точностью до 4-х значащих цифр после десятичной точки.