Автомобиль на круговой дороге Опции

[Kolyancz]

Представьте себе круговую трассу, на которой на произвольном расстоянии размещены заправки, каждая с определенным объемом бензина. Кол-во бензина на всех заправках равно длине дороги. Ваш автомобиль потребляет 100 литров на 100 км и имеет неограниченный бензобак. Вопрос: в какой точке автомобиль должен начать движение, что бы у него никогда не кончался бензин во время поездки?
Дано: 2 массива, 1-ый с объемами бензина на заправках с направлении хода часов, 2-ой с расстояниями между заправками.
Как заставить два массива сравниваться подобным образом?

[volvo]

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

Ответ: в любой. Потому как

автомобиль потребляет 100 литров на 100 км и имеет неограниченный бензобак

С чего бы в неограниченном бензобаке кончился бензин?

А если серьезно - ты бы условие перепроверил, что-то не очень связывается. Например,

Кол-во бензина на всех заправках равно длине дороги

Я уж не говорю о том, что бензин мерить километрами - как то непривычно, вопрос вообще в другом: заправился автомобиль, слил весь бензин, это значит, что больше он на эту заправку приехать не может, или бензин как-то восстанавливается на заправке? Сколько кругов автомобиль должен намотать по трассе? Сколько у него в неограниченном бензобаке есть бензина в начале пути (а то ведь можно и до первой заправки не доехать, если бензина нет изначально)?

[Kolyancz]

Да, условие сложно описать, проще, конечно нарисовать. Когда, я писал о том, что кол-во литров ровнокилометрам, я имел ввиду номинал. 23 литра-23километра. Неограниченый бак вовсе не значит полный бак, это второстепенное условие, типа на всякий случай.
Вот напимер:
На круговой дороге стоят 5 заправок:
Первый массив показывает кол-во литров бензина на этих заправках: 4 7 5 3 4
Второй массив показывает кол-во километров между ними: 7 6 2 3 5
Видно, что всю дорогу можно проехать только лишь тогда, когда начнешь свой путь со второй заправки, т.е.
начинаем на заправке номер два: налили 7 литров проехали 6 километров, остался 1 литр, налили еще 5, проехали 2 км, осталось 4 литра, налили еще 3, проехали 3 км, осталось 4 литра, налили еще 4 литра, проехали 5 км, осталось 3 литра, налили еще 4, проехали 7 км, вот и на той заправки, на которой начали.
Круг один, нужно найти способ проехать круг так, что бы бензин не кончился по пути.

Сообщение отредактировано: Kolyancz - 16.12.2008 18:25

[Lapp]

в какой точке автомобиль должен начать движение, что бы у него никогда не кончался бензин во время поездки?

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

Как заставить два массива сравниваться подобным образом?

Сначала я сделал вторым способом, но разброс во втором массиве получился низкий. Тогда я сделал первый способ. Он значительно улучшил ситуацию, но совсем честным будет только продолжение первого цикла первого способа до достижения t=0.

const
  m=20;

var
  Gas,Way: array[1..m]of integer;
  Start,Tank,t,i: integer;

begin
  { Заполнение массивов }
  Randomize;
  t:=0;
  { первый способ}
  for i:=1 to m do begin
    Gas[i]:=Random(m)+1;
    Way[i]:=Random(m)+1;
    t:=t+Gas[i]-Way[i];
  end;
  for i:=1 to Abs(t) do Inc(Way[Random(m)+1],t div Abs(t));

  { второй способ }
  {for i:=1 to m do begin
    Gas[i]:=Random(m)+1;
    t:=t+Gas[i];
    Way[i]:=0
  end;
  for i:=1 to t do Inc(Way[Random(m)+1]);}

  for i:=1 to m do WriteLn('Pump:',i:3,'     Gas:',Gas[i]:3,'     Way:',Way[i]:3);

  { Езда }
  Start:=0;
  repeat
    Inc(Start);
    Tank:=0;
    i:=Start;
    while Tank>=0 do begin
      Tank:=Tank+Gas[i]-Way[i];
      i:=i mod m+1;
      if i=Start then break
    end;
  until Tank=0;
  WriteLn('start at pump ',Start);
  ReadLn
end.

[Kolyancz]

Lapp, ты действительно гений. Очень красиво решил. Спасибо.