Олимпиадные задачи с рекомендациями к решениям

Задача 65: Автобусный диспетчер (XIV Всероссийская олимпиада по информатике)

На кольцевом маршруте №54 протяженностью S, проходящем мимо пансионата "Энергетик", работает N автобусов. Автобусы пронумерованы числами от 1 до N в порядке их следования по маршруту. Автобус с номером 1 движется за автобусом с номером N. Расписание составлено таким образом, что автобусы движутся с одинаковой скоростью V0 и с равными интервалами между ними. Движение автобусов контролирует диспетчер.
В 12 часов дня некоторые K автобусов одновременно снимаются с маршрута и отправляются на обед. Для восстановления равенства интервалов между автобусами, продолжающими движение по маршруту, потребуется некоторое время Т и, возможно, изменение скорости некоторых автобусов по команде диспетчера. В течение этого времени автобусы должны двигаться с постоянными скоростями из интервала [Vmin, Vmax], назначенными диспетчером. Изменение скорости движения автобуса происходит мгновенно. По истечении времени Т автобусы возобновляют движение по маршруту со скоростью V0.
Требуется написать программу для автоматического диспетчера, которая вычисляет минимальное время Tmin, за которое интервалы движения между оставшимися автобусами станут равными, и скорости движения каждого из них в течение этого времени.

Входные данные
Входной файл bus.in содержит две строки.
В первой строке находятся натуральные числа N, К, S, Vmin, Vmax и V0, где K < N <= 10000, S <= 10000, Vmin < Vmax <= 10000, Vmin <= V0 <= Vmax.
Во второй строке расположены в порядке возрастания K чисел - номера автобусов, снятых с маршрута. Все данные в строках разделены пробелами.

Выходные данные
В первой строке выходного файла bus.out должно находиться значение Tmin.
В каждой из последующих N - K строк должны быть по два разделенных пробелом числа - номер автобуса на маршруте и скорость его движения в течение времени Tmin. Номера автобусов упорядочить по возрастанию. Значения Tmin и скоростей выводить с точностью до 4-х значащих цифр после десятичной точки.

Пример 1
Входной файл bus.in
4 1 60 21 70 60
3
Выходной файл bus.out
0.2041
1 45.5
2 21
4 70

Пример 2
Входной файл bus.in
4 2 40 30 80 50
2 4
Выходной файл bus.out
0
1 50
3 50

Решение: предоставлено С.В. Густокашиным

При решении этой задачи не обошлось без пеньков, о которые я споткнулся, ну а число этих пеньков, как обычно - роковое: три.
Начну со второго, как наиболее крупного и наиболее часто встречающегося. Когда программа уже отлажена и начинаю сверять решение с контрольным примером - числа сходятся, но их порядок другой. Недоумение, поиск ошибок в алгоритме - ничего.
Читаю задачу близким, убеждаю их, что ответы должны идти именно в таком порядке, а иначе автобусы должны ехать задом наперед и тут при очередном прочтении условия осеняет - О, Боже!
Они действительно едут не первый за вторым, второй за третьим и т.д., а второй за первым, третий за вторым и т.д. А это значит мною была невыполнена первая заповедь: внимательно читать условие задачи и не додумывать того, чего нет. Да и рисунки делать только сверяясь с каждым предложением задачи, я ведь нарисовал колечко и написал номера автобусов, только номера-то надо было подписывать согласуясь с условиями, а не просто используя стандартный числовой ряд - 1, 2, 3, 4. Теперь сам разбор и по ходу об остальных "граблях".
Из чего исходим: автобус, проезжающий за время TMin самый длинный путь должен иметь скорость VMax. Значит определив самый длинный путь и имея VMax из условия задачи можно рассчитать TMin. Ну, а имея время и пройденные пути за это время для других автобусов, определить скорости не составит труда.

До определения пройденных путей за время TMin сначала определим расстояния между автобусами после снятия некоторых из них с маршрута. Заодно совместим эту процедуру с запоминанием номеров оставшихся автобусов:

J:= N - K + 1;
for I:= N downto 1 do
if M[I] = 0 then inc(MDist[J])
else begin dec(J); MDist[J]:= 1; MNum[J]:= I; end;
MDist[1]:= MDist[1] + MDist[N - K + 1];

Необходимо отметить, что расстояние между оставшимися автобусами MDist[J] рассчитываем как число первоначальных интервалов между автобусами. Это первый пенек, о который я споткнулся. Сначала, не мало сумняшись, был объявлен массив MDist: array[1..10000] of real; и расчет реального расстояния, возникшего между автобусами. Понятно, что Turbo Pascal 7.0 такого громадного массива вкупе с другими (M[I] и MNum[J]) не потянул, потому появилось объявление MDist: array[1..10000] of integer; и подсчет расстояния в виде числа первоначальных интервалов между автобусами. (этой проблемы можно избежать, если использовать компилятор FreePascal)
Далее привожу текст расчета минимального времени.
Исходим из того, что первый автобус неподвижен (едет с минимальной скоростью), и рассчитываем пути пройденные остальными автобусами, запоминая максимальный и минимальный, чтобы в конце по полученным значениям рассчитать время.

MaxWeg:= 0; MinWeg:= 0; D:= 0; Flag:= false; T:= 0; VVV:= V0;
for I:= 2 to N - K do begin
    Work:= MDist[I] * FInt - LInt + D;
    if abs(Work) < 5.E-10 then Work:= 0;
    if Work <> MaxWeg then Flag:= true;
    if Work > MaxWeg then MaxWeg:= Work;
    if Work < MinWeg then MinWeg:= Work;
    D:= Work;
end;

Теперь определяем время и скорость первого автобуса.

if Flag then begin
T:= (MaxWeg - MinWeg)/(VMax - VMin); VVV:= -MinWeg/T + VMin;
end;
writeln(Out, T:1:4); writeln(Out, MNum[1], ' ', VVV:1:4);

D:= 0;
for I:= 2 to N - K do begin
    Work:= MDist[I] * FInt - LInt + D;
    if Flag then VVV:= (Work - MinWeg)/T + VMin;
    writeln(Out, MNum[I], ' ', VVV:1:4);
    D:=Work;
end;

И на десерт разбор последней ошибки, которая нашлась, что очень огорчило, только при прогоне имеющихся тестов. В результате в расчет максимального и минимального пути была добавлена строка

if abs(Work) < 5.E-10 then Work:= 0;

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