Описание
Метрополитен города Глупова состоит из единственной одноколейной линии. В нулевой момент времени с начальной и конечной станций этой линии навстречу друг другу начинают двигаться два поезда. Их движение подчиняется следующим правилам:

  • Отъезжая со станции, поезд сначала разгоняется, потом некоторое (возможно нулевое) время движется с максимальной скоростью, затем замедляется и, в конце концов, останавливается на очередной станции

  • Поезда останавливаются на всех промежуточных станциях метрополитена

  • На каждой из станций поезда стоят одно и тоже фиксированное время

  • Поезда разгоняются и замедляются с одинаковым, постоянным ускорением

  • Поезда имеют одинаковую максимальную скорость

  • Поезда всегда разгоняются до максимальной скорости, если это не мешает остановиться на следующей станции. Иначе они разгоняются, пока это возможно, а затем сразу же начинают тормозить


Задача
Требуется определить, где и когда поезда столкнутся: "где" определяется расстоянием от начальной станции до места столкновения, а "когда" - временем, когда произойдет столкновение


Входные данные
В первой строке входного файла содержится целое число N (2≤N≤100) - количество станций на линии. Во второй строке записано N-1 вещественное число - расстояние от начальной станции до второй, от начальной до третьей, ..., от начальной до конечной станции. В третьей строке файла записаны три вещественных числа A,V,S - ускорение, максимальная скорость и время пребывания поезда на станции соответственно

Выходные данные
В выходной файл вывести расстояние и время с точностью до двух знаков после десятичной точки


Например:

TRAINS.IN
3
0.25 2.25
1 1 1

TRAINS.OUT
0.38 2.50






Комментарии
Предположим, что поезда, не столкнувшись, проедут друг сквозь друга. Тогда в каждой точке линии второй поезд будет иметь ту же скорость, которую имел в этой точке первый, т.е. он является, в некотором смысле, едущим назад во времени первым поездом. Определим время, которое необходимо, например, первому поезду, чтобы проехать линию от начала до конца. Поделив результат пополам, получим момент, в который оба поезда будут находиться в одной точке. Для нахождения расстояния от начальной станции до найденной точки столкновения остается определить, где в этот момент находится любой из двух поездов

Однако, полученное нами время не обязательно является временем до столкновения. Действительно, если в этот момент поезда находятся на станции, то на самом деле столкновение произойдет в момент приезда на эту станцию последнего из них. Следовательно, в этом случае надо вычислить времена прибытия поездов на данную станцию и взять из них наибольшее

 



 Решение

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 65384,0,655360}
{$A+,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-}
{$N+}

Const InputFile='trains.in';
      OutputFile='trains.out';
      Eps=1e-8;
      epsout=2;
      MaxN=100;
Type Real=Extended;
 Var rs, tm: Array[1..MaxN] Of Real;
     N: Integer;
     cA, cV, cS: Real;
     resa, resb: Real;
     tmacc, rstacc: Real;
 
 Procedure Init;
  Var i: Integer;
   Begin
    resa:=0; resb:=0;
    Assign(Input, InputFile);
     Reset(Input);
      Read(N);
       For i:=1 To N-1 Do Read(rs[i]);
      Read(cA, cV, cS);
     Close(Input);
    tmacc:=cV/cA;
    rstacc:=cA*Sqr(tmacc)/2;
    For i:=N-1 DownTo 2 Do rs[i]:=rs[i]-rs[i-1];
   End;
 
 Function Eq(Const a, b: Real): Boolean;
  Begin
   Eq:=Abs(a-b)<=Eps;
  End;
 
 Function More(Const a, b: Real): Boolean;
  Begin
   More:=a-b>Eps;
  End;
 
 Function Min(Const a, b: Real): Real;
  Begin
   If More(a, b) Then Min:=b Else Min:=a;
  End;
 
 Function Max(Const a, b: Real): Real;
  Begin
   If More(a, b) Then Max:=a Else Max:=b;
  End;
 
 Function TimeAcc(Const rst: Real): Real;
  Begin
   If More(rst, rstacc) Then TimeAcc:=tmacc+(rst-rstacc)/cV
    Else TimeAcc:=Sqrt(2*rst/cA);
  End;
 
 Function TimeAccBrak(Const rst: Real): Real;
  Begin
   TimeAccBrak:=2*TimeAcc(rst/2);
  End;
 
 Procedure Fill;
  Var i, j: Integer;
   Begin
    For i:=1 To N-1 Do
        tm[i]:=TimeAccBrak(rs[i]);
   End;
 
 Procedure Done;
  Begin
   Assign(Output, OutputFile);
    Rewrite(Output);
     WriteLn(resa:0:epsout, ' ', resb:0:epsout);
    Close(Output);
   Halt;
  End;
 
 Procedure CheckAtStation;
  Var i, j: Integer;
      sclf, scrg, rst: Real;
   Begin
    sclf:=(N-3)*cS; rst:=0;
     For i:=1 To N-2 Do Begin
      sclf:=sclf+tm[i];
      rst:=rst+rs[i];
     End;
    scrg:=tm[N-1];
    For i:=N-2 DownTo 1 Do Begin
     If Not More(Max(sclf, scrg), Min(sclf, scrg)+cS) Then Begin
       resa:=rst;
       resb:=Max(sclf, scrg);
       Done;
     End;
     sclf:=sclf-tm[i]-cS; scrg:=scrg+tm[i]+cS;
     rst:=rst-rs[i];
    End;
   End;
 
 Procedure CheckOnRoad(ptm: Real);
  Var i: Integer;
      rsc: Real;
   Begin
    rsc:=0;
    resb:=ptm;
    i:=1;
    While More(ptm, tm[i]+cS) Do Begin
      rsc:=rsc+rs[i];
      ptm:=ptm-tm[i]-cS;
      Inc(i);
     End;
    If More(tm[i], 2*tmacc) Then Begin
       If More(ptm, tmacc) Then Begin
          If More(ptm, tm[i]-tmacc) Then
             rsc:=rsc+2*rstacc+(tm[i]-2*tmacc)*cV-Sqr(tm[i]-ptm)*cA/2
           Else rsc:=rsc+rstacc+(ptm-tmacc)*cV
        End
        Else rsc:=rsc+Sqr(ptm)*cA/2;
     End
    Else Begin
      If More(ptm, tmacc) Then rsc:=rsc+2*rstacc - Sqr(ptm-tmacc)*cA/2
       Else rsc:=rsc+Sqr(ptm)*cA/2;
    End;
    resa:=rsc;
    Done;
   End;
 
Var tfa, tfb, tsa, tsb: Array[1..MaxN] Of Real;
 
 Procedure CheckOnRoadVer1;
  Var i: Integer;
      psm: Real;
   Begin
    tfa[1]:=0; tfb[1]:=tm[1];
    tsa[N-1]:=0; tsb[N-1]:=tm[N-1];
     For i:=2 To N-1 Do Begin
      tfa[i]:=tfb[i-1]+cS; tfb[i]:=tfa[i]+tm[i];
     End;
     For i:=N-2 DownTo 1 Do Begin
      tsa[i]:=tsb[i+1]+cS; tsb[i]:=tsa[i]+tm[i];
     End;
    For i:=1 To N-1 Do
     If Not More(Max(tfa[i], tsa[i]), Min(tfb[i], tsb[i])) Then Begin
      psm:=(Max(tfa[i], tsa[i])+Min(tfb[i], tsb[i]))/2;
      CheckOnRoad(psm);
      Done;
     End;
   End;
 
 Procedure Solve;
  Var a, b, stm: Real;
      i: Integer;
   Begin
    stm:=(N-2)*cS;
    For i:=1 To N-1 Do stm:=stm+tm[i];
    stm:=stm/2;
     CheckAtStation;
    CheckOnRoadVer1;
   End;
 
BEGIN
 Init;
  Fill;
  Solve;
 Done;
END.

 

© Особенности национальных задач по информатике