ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1031. Железнодорожные билеты

O(n) and funny error
Послано Vlad Veselov 11 сен 2003 21:11
My AC code is those:
  Program RailwayTickets;
   Const MaxN = 10000;
   Var   L,C                : Array [1 .. 3] Of LongInt;
         Stops              : Array [1 .. 3,1 .. MaxN] Of LongInt;
         Costs,D            : Array [1 .. MaxN] Of LongInt;
         Start,Finish,I,N   : Word;
         J                  : Byte;
         S,Min,T            : LongInt;

   BEGIN   {
    Assign(Input,'1031.in');   Reset(Input);
    Assign(Output,'1031.out'); ReWrite(Output);}
    Read(L[1],L[2],L[3],C[1],C[2],C[3],N,Start,Finish);
    D[1] := 0;
    For I := 2 To N Do
     Read(D[I]);
    If Start > Finish
     Then begin
           I := Start;
           Start := Finish;
           Finish := I;
          end;
    Stops[1,Start] := Start;
    Stops[2,Start] := Start;
    Stops[3,Start] := Start;
    For I := Start + 1 To Finish Do
     For J := 1 To 3 Do
      begin
       S := Stops[J,I - 1];
       While D[I] - D[S] > L[J] Do
        Inc(S);
       Stops[J,I] := S;
      end;
    Costs[Start] := 0;
    For I := Start + 1 To Finish Do
     begin
      Min := MaxLongInt;
      For J := 1 To 3 Do
       If Stops[J,I] <> I
        Then begin
              T := Costs[Stops[J,I]] + C[J];
              If T < Min
               Then Min := T;
             end;
      Costs[I] := Min;
     end;
    WriteLn(Costs[Finish]);
   END.
I think that it has complexity O(3 * N). Am I wrong?
I use Turbo Pascal 7.0, because shell of Free Pascal is
unstable on my computer. That is the why when I post my solution
first time I forgot to change MaxN to 10000 and got TLE :).
P.S. Sorry for bad English.