Псевдо удавчик Опции

[arhimag]

Люди помогите решить вот такую задачу.
Удавчик ползает по прямой и изначально он пробегает 1см в сек. Когда удавчик наползает на спидап его скорость удвавается. На вход подается координата начала, конца, и кол-во бонусов и их координаты. На до найти путь который займет наименьшее кол-во времени.
и вывести проходимые спидапы(их координыты) и общее время все происходит на прямой.
заранее спасибо

[Lapp]

Немного подумав, я пришел к выводу, что проблема не так сложна, как сначала мне показалась..
В любой текущий момент времени удав может двигаться влево или вправо. Поворачивать на пустом месте (без спидапа) для удава никакого резону нет, так что будем рассматривать только моменты прохождения спидапов. В любой такой момент перед удавом стоит дилемма: двигаться влево или вправо - то есть двоичный выбор. Таким образом, все возможные пути представляют собой двоичные числа (0 означает движение влево, а 1 - вправо) длины не больше М разрядов (М - число спидапов, включая начальную точку).

Программных реализации этого дела на ум приходят две:
1. Перебор всех двоичных чисел с подсчетом времени путешествия удава по схеме каждого двоичного числа.
2. Рекурсивная процедура передвижения на шаг влево или вправо.

В каждой реализации пройденные точки помечаются как неактивные и на следующем шаге не учитываются.
Рекурсия более ресурсоемка (как по отношению к памяти, так и ко времени), но проще в реализации (по крайней мере, для меня), так что я выбрал ее.

Теперь слушай сюда, arhimag. Я сейчас выложу полностью работающую прогу (даже с некоторыми с комментариями).. Но если ты, arhimag, не напишешь тут в ближайшие дни полный разбор этой программы - то, arhimag, пеняй на себя, arhimag. Потому что какой бы ты там архи- ни был бы маг, а volvo меня тут уроет и еще потопчется потом на холмике!! И будет прав.. потому что надо заранее постить тему и участвовать в обсуждении активно, а не кричать, что помогите-гибнешь и все такое.. Короче, arhimag, если не появится подробного разбора этой проги в течение нескольких дней - я клянусь тебе, arhimag, я больше ни разу тебе тут не отвечу! Ни на самый маленький вопросик!! И, думаю, ко мне все остальные присоединятся..
Ты понл, да??
Вот, а теперь - дело..

Программа использует файл с названием speedups.txt. В нем заводятся координаты спидапов, а также координаты начального положения удава и финиша. Все координаты должны быть обязательно упорядочены по возрастанию! Координаты старта вводятся среди спидапов (как бы он начинает движение со спидапа). Координата финиша всегда максимальная! Случай, когда финиш находится слева моя прога не умеет решать. Формат файла такой:
В первой строчке два целых числа:
- сначала кол-во спидапов плюс 2 (то есть полное число спидапов плюс старт и финиш),
- потом номер спидапа начальной позиции (старта).
В последующих строках идут координаты спидапов, старта и финиша по возрастающей, по одному числу на строку. Вот пример файла (комментарии в скобках в файле не должны присутствовать!):

7 3 (семь строк ниже, третье число - старт)
-10
-3
1 (это старт)
2
15
20
30 (это финиш)

А теперь сама прога..

const
  N=100;

type
  tInt=integer;
  tReal=real;
  tSpeedUp=record
    x:integer;
    active:boolean
  end;

var
  time:tReal=1E99;
  l:integer=0;

var
  x,p,px:array[1..N]of integer;
  a:array[1..N]of boolean;
  f:text;
  s,m,i,lx:integer;

function Go(s:integer;v,t:tReal):boolean;
var
  sl,sr:integer;
begin
  Inc(l);p[l]:=s;
  if s=m then begin        { finish }
    if time>t then begin     
      time:=t;
      lx:=l;
      px:=p
    end
  end
  else if a[s] then begin     { active speedup }
    a[s]:=false;
    sl:=s;
    repeat Dec(sl) until (sl=0)or Go(sl,v*2,t+(x[s]-x[sl])/v);   { Move left }
    sr:=s;
    repeat Inc(sr) until (sr>m)or Go(sr,v*2,t+(x[sr]-x[s])/v);    { Move right }
    a[s]:=true;
    Go:=true
  end
  else Go:=false;       { passive speedup }
  Dec(l)
end;

begin
  Assign(f,'speedups.txt');ReSet(f);
  ReadLn(f,m,s);
  for i:=1 to m do begin
    ReadLn(f,x[i]);
    a[i]:=true
  end;
  Close(f);
  Go(s,1,0);
  WriteLn('Min Time:',time:10:6);
  Write('Path:');
  for i:=1 to lx do Write(px[i]:4);
  ReadLn
end.