Задача 11-той Кировской областной олимпиады

"Мотоциклисты"

С.М.Окулов

Среди мотоциклистов г. Кирова популярно следующее соревнование: на одной из улиц города выбирается прямой участок, на котором установлено N (1ЈNЈ100) светофоров, имеющих только красный и зеленый цвета. Мотоциклист проезжает выбранный участок на постоянной скорости, причем нарушать правила дорожного движения, т.е. проезжать перекресток на красный свет, категорически запрещается, кроме случаев, когда мотоциклист пересекает перекресток в момент переключения светофоров. Мотоциклист, изменивший скорость движения, либо проехавший на красный свет, либо выбравший скорость, меньшую 5 м/с, дисквалифицируется. Побеждает мотоциклист, проехавший трассу за минимальное время. Известный мотоциклист Федя обратился к представителям науки, чтобы они помогли ему выбрать оптимальную скорость движения по трассе.

Входные данные. В первой строке файла INPUT.TXT записано N — число светофоров. В следующей строке N+1 число: первое — расстояние от точки старта до первого светофора, второе — расстояние между первым и вторым светофорами, …, последнее число — расстояние от последнего светофора до точки финиша (числа из интервала от 1 до 100000). В третьей строке записаны N чисел — время работы каждого светофора в красном и зеленом режимах (оно одинаково). Время — число из интервала от 1 до 300.

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

В файле OUTPUT.TXT должно быть записано одно число (с точностью до четырех знаков) — искомая скорость или сообщение “NO”, если решения нет.

Пример

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

3
200 100 200 200
2 1 9

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

55.5556

 

Рис. 1

Идея решения. На рисунке по горизонтальной оси откладываем расстояния, а по вертикальной — время. Время работы каждого светофора в красном режиме выделено на соответствующих расстояниях “черным отрезком”. Каждой скорости движения мотоциклиста соответствует наклонная прямая. Для решения задачи необходимо провести прямую из начала координат с наименьшим угловым коэффициентом, проходящую через “светлые” участки рисунка. Обратим внимание на то, что “лучшая” прямая касается хотя бы одного отрезка в верхней точке. Действительно, если она не касается ни одного отрезка в верхней точке, то ее можно сдвинуть (“повернуть”) вниз, уменьшая при этом угол, т.е. увеличивая скорость, до соприкосновения с первым отрезком. Из вышесказанного следует решение: необходимо проверить все возможные “верхние” точки “темных отрезков” на предмет их принадлежности искомым прямым и выбрать лучший.

Определим данные.

Type Real=Extended;
Const InputFile='Input.TxT';
OutputFile='Output.TxT';
Eps=1e-5;
MaxN=100;
Var N:Integer;
Rs, WhRd: Array[0..MaxN+1] Of Real;
Can: Boolean;
ResMax: Real;

Процедуры ввода и вывода данных и основная программа представлены ниже.

Procedure Init;
Var i: Integer;
Begin
  ResMax:=-MaxLongInt;
  Assign(Input, InputFile);Reset(Input);
  Read(N);
  For i:=1 To N+1 Do Begin
    Read(Rs[i]);
    If i>1 Then Rs[i]:=Rs[i] + Rs[i-1];
    {Считаем расстояния от начальной точки}
  End;
  For i:=1 To N Do Read(WhRd[i]);
  {Время работы каждого светофора}
  Close(Input);
End;

Procedure Done;
Begin
  Assign(Output, OutputFile);
  Rewrite(Output);
  If Can Then WriteLn(ResMax:0:4)
   Else WriteLn('NO');
  Close(Output);
End;

{Основная программа}

Begin
  Init; Solve; Done;
End.

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

Function More(a, b:Real):Boolean;
  Begin
    More:=(a-b)>Eps;
End;

Function Eq(a, b:Real):Boolean;
Begin
    Eq:=Abs(a-b)<Eps;
End;

Пусть дана скорость движения мотоциклиста R. Необходимо определить, можно ли с этой скоростью проехать все светофоры. Эта подзадача решается с помощью двух функций — IfMay и IfPoss.

Function IfPoss(Const k: Integer;Const Tm: Real): Boolean;
Var d: Real;
Begin
   d:=(Tm/WhRd[k]);
   IfPoss:=Eq(d, Round(d)) And Eq(Frac(Int(d)/2), 0.5);
   {значение d кратно времени работы светофора и нечетно}
End;

Function IfMay(Const R: Real): Boolean;
Var i: Integer;
Begin
   IfMay:=False;
   For i:=1 To N Do Begin {i — номер светофора}
    If Not IfPoss(i, Rs[i]/R) Then Exit;
    {R[i]/R - время, в которое мотоциклист доедет со
    скоростью R до светофора с номером i}
    {если для каждого значения i IfPoss возвращает
          значение true, т.е. мотоциклист может проехать
    через данный светофор, то скорость R допустима и
    IfMay присваивается значение true}
   End;
  IfMay:=True;
End;

Последняя, ключевая процедура — Solve, в которой производится перебор всех верхних точек отрезков.

Procedure Solve;
Var i: Integer;
Begin
  Can:=False;
  For i:=1 To N Do TryFind(i);
  {А почему не сделать еще одну процедуру, которая будет
   осуществлять проверку прямых, проходящих через
   "верхние" точки работы светофора с номером i?}
End;

Procedure TryFind(k: Integer);
  Var i:Integer;
    R: Real;
  Begin
   i:=1;
   R:=Rs[k]/(WhRd[k]*i);
   While (Not More(5, R)) And More(R, ResMax) Do Begin
     If IfMay(R) Then Begin
       {если мотоциклист может проехать на этой скорости все
        светофоры, то одно из решений найдено, следующие
        "верхние" точки этого светофора проверять нет смысла —
        для них скорость мотоциклиста будет меньше}
        ResMax:=R;Can:=True;Exit;
     End;
     Inc(i,2);{переходим к следующему переключению светофора
               с красного режима на зеленый}
     R:=Rs[k]/(WhRd[k]*i);{вычисляем скорость}
   End;
End;

 TopList