Xpoint
   [напомнить пароль]

Задачка

Метки: [без меток]
2006-09-27 13:29:52 [обр] Иванов Михаил aka Ivanych(0/70)[досье]

Мне тут рассказали задачу, в которой я в данный момент не помню точных цифр. Впрочем, думаю, конкретные цифры несущественны. Поэтому сформулирую в общем виде:

Обезьяне нужно пройти L километров. На каждый километр пути (в любую сторону) обезьяна съедает один банан. За один раз обезьяна может унести N бананов (N<L). Сколько бананов (минимум) должно быть изначально?

спустя 2 часа 24 минуты [обр] Сергей Круглов(10/2057)[досье]
Эээ... что-то это какая-то неправильная/неполная задача.
L километров - это расстояние по прямой между начальной и конечной точками маршрута?
Бананы обезьяне где выдаются?
спустя 26 минут [обр] Lynn «Кофеман»(1/571)[досье]

Старая задача. Встречал её в вариации грузовика, которому надо пересечь пустыню.

Сергей Круглов[досье]
Если я правильно помню, бананы выдаются в точке старта, но обезьяна в любом месте пути может сделать склад бананов.

спустя 53 минуты [обр] Иванов Михаил aka Ivanych(0/70)[досье]

Сергей Круглов[досье]

L километров - это расстояние по прямой между начальной и конечной точками маршрута?

Да.

Бананы обезьяне где выдаются?

В начале пути.

спустя 18 минут [обр] Иван Неретин(0/8)[досье]
А, помню. Там какой-то экспоненциальный от расстояния рост времени, потребного на выстраивание цепочки складов.
спустя 1 день 19 часов [обр] Alexander O(6/460)[досье]
# для нечетного числа N 
# Базы будут через каждые (N-1) / 2 километров
# Обезьяна загружается по полной на текущей базе, идет на следующую базу, оставляет там 1 банан и возвращается
# так она накапливает достаточно бананов, чтоб дойти до L не возврашаясь а текущую базу

# perl
sub bananas {
   my $L = shift;  # расстояние , которое нужно пройти
   my $N = shift;  # сколько бананов можно унести за раз
   
   my $b0 = $L % $N || $N;  # сколько бананов нужно на последней базе, чтобы прийти к финишу без бананов
   my $l = 2 * ($L - $b0) / $N;  # cколько баз потребуется
      
   # рекурсивная функция. Считает сколько бананов нужно в нулевой базе, чтобы до базы $l донести $b0 бананов
   sub req { 
      my $i = shift || 0;
      return $b = $i < $l-1
             ? $N ** req($i + 1) + ($N-1) / 2
             : $b0;
   }

   return req();         
}
спустя 1 час 23 минуты [обр] Иванов Михаил aka Ivanych(0/70)[досье]
100000004.5 бананов?! Нет, чтом что-то около 30 бананов было.
спустя 4 минуты [обр] Alexander O(6/460)[досье]
Иванов Михаил aka Ivanych[досье] это для каких N L ?
спустя 1 минуту [обр] Иванов Михаил aka Ivanych(0/70)[досье]

Т.е. это результат bananas(18, 10)

Цифры такие, уточнил, говорят - 33 банана надо.

спустя 2 часа 48 минут [обр] Alexander O(6/460)[досье]
Иванов Михаил aka Ivanych[досье] Значит, я тупее, чем обезъяна. Каким образом будет 33?
спустя 12 минут [обр] Иванов Михаил aka Ivanych(0/70)[досье]

Я сам не знаю правильного решения.

Но явно не миллионы. Методом тыка, просто на бумажке рисуя, у меня получается в пределах сотни.

Интуитивно чувствую, что тут надо найти оптимальный отрезок перемещения, на котором бананов будет перенесено максимум, а длина отрезка будет минимум. Только не понимаю, как это выразить математически.

Допустим, если взять 10 бананов и начать совершать перемещения туда-сюда, то:
1 км - перенесем 8 бананов.
2 км - 6 бананов
3 км - 4 банана
4 км - 2 банана
5 км - 0 бананов.

Вот какой-то из этих отрезков (ну, наверно, за исключением 5 км), является оптимальным, но какой - не понимаю.

спустя 6 минут [обр] Иванов Михаил aka Ivanych(0/70)[досье]
А, еще в условие оптимальности, видимо, нужно включить требование, чтобы максимальное количество перенесенных бананов было перенесено за минимальное количество "пустых" перемещений. "Пустое" - это когда обезьяна возвращается и при этом бананы только тратятся, а вперед не перемещаются.
спустя 13 минут [обр] Алексей Севрюков(2/1280)[досье]
спустя 24 секунды [обр] Илья Cтpeльцын aka SelenIT(2/171)[досье]
IMHO, нужно как-то за 15 перемещений построить цепочку из 8 бананов через каждый километр. Тогда обезъяна сможет спокойно взять последние 10 бананов и, не тратя их, пройти эти 8 км, а оставшийся путь преодолеть уже на запасе. Но вот как построить эту цепочку — пока не соображу. Думаю в том направлении, что в начале придется выкладывать на каждом километре по 2 или 3 банана, обеспечивая себе запас на обратный путь и следующие перемещения.
спустя 21 минуту [обр] Илья Cтpeльцын aka SelenIT(2/171)[досье]
Хотя нет, так не получится - это ведь даже по одному разу туда-обратно эти 8 км пройти не хватит...
спустя 1 час 21 минуту [обр] Евгений Петров(0/1055)[досье]
Насколько я понял, задача разбивается на построение цепочки складов, последний из которых будет находиться за N километров до финиша и на котором будет N бананов. И все сводится к определению целесообразности (время/количество пройденного пути/количество съеденных бананов).
Если наложить ограничение, что обезьяна ходит целое количество километров, то одна крайность - построение складов через каждый километр, другая - через N/2-1 километров. Где-то между ними и лежит золотая середина:)
спустя 2 часа 4 минуты [обр] Илья Cтpeльцын aka SelenIT(2/171)[досье]

Евгений Петров[досье]
Базы на каждом километре - еще не крайность). Можно делать базы каждые полкилометра, тогда энергии одного банана хватит на перемещение между базами (на полкилометра) целых 10 бананов без потерь. Если у обезъяны есть свободное место, она подбирает бананы по пути (до максимума) и тащит вперед. Распределение бананов по километрам получается следующее (звездочкой отмечено местоположение обезъяны):

Итерация (aka "съедено бананов")0км0.511.522.533.544.555.566.57
033*
122*10
211*20
32010*
41019*
528*
617*10
76*20
81510*
9519*
1013*10
113*19
121110*
13119*
149*10
15810*
167*10
17610*
185*10
19410*
203*10
21210*
2211*

Теперь, съев один банан, обезъяна запасется энергией, чтобы донести оставшиеся 10 до 8-го километра, после чего ей как раз хватит пищи на оставшиеся 10 километров пути.

спустя 1 час 9 минут [обр] Евгений Петров(0/1055)[досье]

Илья[досье], ну знал, что стоит упоминуть про "нестандартные" пути:) Я описал самый примитивный способ. Само собой, можно построить алгоритм с использованием промежуточных складов. Ну, и я сразу оговорился про ограничения - про возможно целое число километров, пройденное обезьяной.

P.S. Не могу не заметить, что в приведенной схеме 10 то отмечено звездочкой, то нет... Я понимаю, что проставление этих звездочек - отдельный труд, и в его процессе могла возникнуть ошибка в корреляции.
И, может, чего-то не догоняю, но цепочка 17* 10 6* 20* вызывает сомнения... Как можно принести 10 бананов, взяв только 6???

спустя 50 минут [обр] Илья Cтpeльцын aka SelenIT(2/171)[досье]

Евгений Петров[досье]
На самом деле подсказка, что число километров между складами не обязательно целое, была по ссылке, которую дал Алексей Севрюков[досье], а я лишь нагло ей воспользовался.

В моем алгоритме обезъяна всегда останавливается на целых километровых отметках. С каждым съеденным бананом она либо продвигается вперед на 1 км (забирая по пути, сколько может унести, бананов из промежуточного склада), либо совершает "челночный рейс" к предыдущему либо следующему складу (перенося 10 бананов вперед) и возвращается на то же место. Так что в цепочке 17* 10 — 6* 20 все нормально: один банан из 17 обезъяна съела, на его энергии отнесла 10 из оставшихся 16 на следующую базу и вернулась. На следующем шаге она съест 1 из 6, понесет 5 на следующую базу, там, не останавливаясь, доберет еще 5 и остановится с 10 на следующем километре.

А вот между 9 и 10 шагами что-то обезъяна у меня слишком разбегалась — тут я в самом деле ошибся. В такой схеме придется ей сделать "ходку" ради всего 5 бананов, так что на 10 шаге все 23 банана окажутся на 2-м километре. Видимо, корни ошибки тянутся с 4-го шага, и тащить бананы вперед нужно всегда, когда есть возможность. Уже проверяю эту версию...

спустя 31 минуту [обр] Alexander O(6/460)[досье]
Моя обезъяна пройдет путь, съев 56 бананов.
На картинке по горизонтали — километры, по вертикали — номер шага (снизу вверх)
Красным отмечено положение обезьяны на каждом шаге
Цифрами отмечено количество бананов на текущем шаге (если цифр нет, значит бананов ноль)
Обезьяна стремится к тому, чтобы было как можно меньше порожних шагов.
спустя 3 часа 14 минут [обр] Илья Cтpeльцын aka SelenIT(2/171)[досье]
По уточненным данным, моей обезъяне необходимо 34 банана на 17 километров пути (как по вышеприведенной ссылке) и 41 банан — на 18 километров (соответственно, 33 и 40 — если обезъяна отправляется в дорогу полностью сытой). Алгоритм элементарный, что-то вроде такого:
съесть 1 банан из доступных в месте нахождения;
если (на предыдущей промежуточной базе >N бананов) {
   принести N бананов с предыдущей базы и вернуться
} иначе {
   если (на предыдущей базе есть бананы) {
      забрать остаток с предыдущей базы и вернуться
   }
   если (бананов в месте нахождения >N) {
      отнести N бананов на следующую базу и вернуться
   } иначе {
      перенести бананы на 1 км вперед,
      при возможности добрав их до N на следующей промежуточной базе;
   }
}
спустя 22 часа [обр] Alexander O(6/460)[досье]

Вобщем, чтобы использовать минимальное число бананов, нужно из каждой базы выходить с полной загрузкой. Если не привязываться к целочисленным отметкам километров, то сделать это возможно.
На картинке красным отмечен путь движения обезъяны. Синие точки — базы. Подписи к точкам — расстояние, на котором находится база. Высота точек — максимальное кол-во бананов, находящихся на базе, достаточное для того, чтобы обезъяна могла двигаться к следующей базе.

# perl
sub bananas {
   my $L = shift;  # расстояние , которое нужно пройти
   my $N = shift;  # сколько бананов можно унести за раз
   my $k = 0;
   while ($L > $N/(2*$k + 1)) { # считаем сколько баз $k нужно
      $L -= $N/(2*$k + 1); 
      $k++;
   }
   # после цикла в $L получилось расстояние до первой базы
   return  $k*$N            # кол-во бананов на первой базе
         + ($k*2+1)*$L;   # + накладные расходы на заполнение первой базы
}

bananas(18,10) = 51.4

спустя 1 день 8 часов [обр] Иванов Михаил aka Ivanych(0/70)[досье]

Ну, я не автор задачи, но думаю, что бананов должно быть обязательно целое число. И километры можно ходить только целые.

Я сейчас думаю в таком направлении:

Нужно сначала определить, на какое расстояние обезьяна унесет N-10 бананов. Т.е. на запасе в 10 бананов нужно перетащить максимально далеко 23 банана. Там и будет первая база.

Потом аналогично для оставшихся бананов.

спустя 2 часа 24 минуты [обр] Илья Cтpeльцын aka SelenIT(2/171)[досье]
Иванов Михаил aka Ivanych[досье]
А чем полкилометра взад + полкилометра вперед — не целый километр?
спустя 21 час [обр] Иванов Михаил aka Ivanych(0/70)[досье]

Илья Cтpeльцын aka SelenIT[досье]
Да мне не жалко, ходите хоть дробями:)

А я буду ходить дискретно, по километру:)

Powered by POEM™ Engine Copyright © 2002-2005