Обезьяна раздобыла 1000 бананов ей нужно побольше бананов перенести домой за 100 км по единственной дороге. Можно создавать промежуточные запасы и возвращаться. Есть две проблемы
- за один раз она может нести 100 бананов
- после каждого километра нужно подкрепиться и съесть один банан.
Сколько максимально бананов может она доставить домой?

800&

когда она идет пустая она должна жрать 1 бнан на километр?

(2) да

(0) А если не съест 1 банан за километр - сдох*ет? :))

(4) примерно так

92

(6)
фига се

(6) может чуть юольше за счет оптимизации последнего рывка, счас посчитаю

а на обратном пути она тоже должна лопать по 1шт/км?

ровно 100 бананов

(9) да
(10) ждем расчет

vde69 впервые не стал спрашивать "зачем такие задачи?", а стал решать

Взяла 100 бананов, прошла 25 км, оставила заначку из 50 бананов (по дороге слопала 25 бананов, 25 оставила на обратную дорогу). Вернулась, взяла 100 бананов, пошла с ними до заначки, из которой забрала 25 бананов (больше не унести), прошла еще 25 км, оставила заначку из 50 бананов, вернулась к первой заначке, взяла 25 бананов (чтобы есть пока идет к оставшимся 800), ну и т.д.
(9) да

(11) вру, 96 шт

каждый км вычитам 2 банана умноженые на окрВВерх предыдущего кол-ва

100 бананов у нее останется на 97 км, последний рывок она пойдет не возвращаясь

(12) я в екселе :)

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

меня волнует другое - нафига такая прогулка нужна? трансакционные издержки несопоставимы..

(16) он домой не вернется :)

По мотивам (13): "Взяла 100 бананов, прошла 50 км и... вернулась обратно, уставшая как собака... А чего вы хотели? Обезьяна ведь! :))

Ей, кстати, необязательно бегать туда-сюда 100 км. Она может перетащить остатки от тонны на какое-то расстояние, потом дальше таскать. Километраж будет меньше.

(16) по-любому всё на работе выпьет
(18) точнее: он домой пиво не потащит

(19) Она лопнет раньше, обжора :=)

(10) Проще негров за 100 бананов нанять - пусть перетащат за нее :)

(13) получается чтобы 1000 перенести на 25 км затратит 475 бананов, остаток 525.
на следующие 25 км надо 6 ходок, при этом при последней ходке только 25 бананов - это только до заначки дойти :) получается надо таскать (остаток)/Кол-во ходок

(13) а может так:
1-2км: сходила 20 раз,съела 20 бананов
2-3км: сходила 20 раз,съела 20 бананов
3-4км: сходила 20 раз,съела 20 бананов
4-5км: сходила 20 раз,съела 20 бананов
5-6км: сходила 20 раз,съела 20 бананов
6-7км: сходила 18 раз,съела 18 бананов
...
под конец бананов останется меньше, следовательно ходок будет меньше

+25 это когда жадная обезьяна таскает всю партию на каждый км

(25) на последнюю партию затраты меньше: обратно возвращаться не надо

если ходить меньше чем по 1 км. обезьяна не может - 138 бананов, перетаскивая каждый раз кучу на 1 км. При отрезках по 10 км - только 100, при 25 - 50...
количество ходок на каждом этапе ОКРВВЕРХ(колич. бананов на предыдущей остановке/100), количество затрат (2 * количество ходок - 1) * длина маршрута.
P.S. Но это если она есть банан пока идет очередной километр, если она съедает банан в конце каждого километра - она может на обратный путь брать на 1 банан меньше и формулы поменяются.
P.P.S. в идеале, при отрезках пути стремящимся к 0 - количество бананов дотащеных до дома - стремится к 900...

Резюме: Пусть все жрет на месте

(29)+10500
оставляет себе на дорогу 100 бананов, остальные 900 жрет. самый отличный вариант

Перерасчитал кучу вариантов... Итого: обезьяна сожрала все бананы, не дойдя до конечного пункта... Мне какая-то неправильная обезъяна досталась :(

(31) 96 бананов дотащила

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

(33) 96 недоеденных бананов... Т.е., ты старался, тащил, а теперь останутся они лежать, абсолютно бесполезные для тебя лично :=)

(34)ДА! //расплакался

Ужасть, как грустно: на похоронах старой обезьяны присутствовали 96 приглашенных...

прибыл в конечную точку имея 148 бананов, но один нужно сожрать.
при этом на 82 км оставил один банан (возвращаться было не резон), ходка туда обратно два км сожрет два банана.

Интересно, а если провести эксперимент реально, что будет делать обезьяна?:)

"Интересно, а если провести эксперимент реально, что будет делать обезьяна?:)"
Умная обезьяна скажет, что где бананы - там и дом. И никуда не пойдет вообще...

Если брать неизменный размер партии (1000 штук) - то обезьяна для их переноса будет тратить по 20 бананов на каждый километр (при этом принимаем, что и в последний переход обезьяна тоже возвращается). При таких условиях на весь путь потребуется 2000 бананов. Соответственно возможности экономии заключаются в двух моментах: 1) уменьшение количества переходов, из-за уменьшения переносимой партии бананов (900, 800); 2) экономия на последнем переходе, когда не тратится энергия на возврат. По моему - максимальная экономия будет при отрезке, на который обезьяна переносит бананы - стремящемся к нулю. Можно, например, рассмотреть ситуацию при отрезке в 0.1 км.
З.Ы. При отрезке в 50 км - все бананы уйдут на ходьбу,
при отрезке в 49.5 км - за первые 9 переходов на 49.5-м километре останется 9 бананов, при последнем переходе, взяв 100 бананов в начальной точке, к 49.5-му километру подойдет с 51 бананом, далее забрав находящиеся там 9 бананов к конечной точке подойдет с этими 9-ю бананами
при отрезке в 49 км - за первые 9 переходов на 49-м километре останется 18 бананов, при последнем переходе, взяв 100 бананов в начальной точке, к 49-му километру подойдет с 51 бананом, далее забрав находящиеся там 18 бананов к конечной точке подойдет с этими 18-ю бананами
при 25-км - остается еще больше т.д.

(40) а в целых числах пожалуйста

(41) про целые ничего сказано не было

(0) Нисколько.
Если зараз сожрать 903 банана - то любая обезьяна сдохнет на третьей сотне.

90?

Решение то простое...
900*0.8+100*0.81

Что-то я просчитался..

(45) а решение?

не эффективная обезьяна какая-то ))

(47) Решил, сейчас оформлю.

Хотя нет...

Да чо тама решать?
сначала таскает все в одну сторону, сжирая на каждом километре по 1, за ходарь туда и на каждом меньше последнего, когда назад... А потом от последней точки, собрать остатки - ходить назад... оппа.
Похоже, ничего она не донесет.

Я насчитал 148 бананов.

Порожняком расход топлива д/б меньше...

На 0 километре 1000 бананов.
На 1 километре  981 банан: 9 ходок туда-обратно и одна туда, то есть
1000 - (2*9+1) = 981 банан.
С 1-го по 6 километр на каждом километре теряется 19 бананов.
На 6 километре 1000 - 6*19 = 896
с 7-го по 12 километр на каждом километре теряется 17 бананов.
На 12 километре 896 - 6*17 = 794
с 13-го по 19 километр на каждом километре теряется 15 бананов.
На 19 километре 794 - 7*15 = 689
с 20-го по 26 километр на каждом километре теряется 13 бананов.
На 26 километре 689 - 7*13 = 598
с 27-го по 35 километр на каждом километре теряется 11 бананов.
На 35 километре 598 - 9*11 = 499
с 36-го по 46 километр на каждом километре теряется 9 бананов.
На 46 километре 499 - 11*9 = 400
с 47-го по 61 километр на каждом километре теряется 7 бананов.
На 61 километре 400 - 15*7 = 295
с 62-го по 80 километр на каждом километре теряется 5 бананов.
На 80 километре 295 - 19*5 = 200
с 61-го по 100 километр на каждом километре теряется 3 банана.
На 100 километре 200 - 20*3 = 140 бананов

(54)
   Всего=1000;
   Для сч=1 по 100 Цикл
       ОсталосьПеренести=Всего;
       
       Пока Истина Цикл
           Если ОсталосьПеренести>100 Тогда
               ОсталосьПеренести=ОсталосьПеренести-100;
               Всего=Всего-2;
           Иначе
               ОсталосьПеренести=0;
               Всего=Всего-1;
               Прервать;
           КонецЕсли;  
       КонецЦикла;    
       
       Сообщить("Километр "+сч+" Осталось"+Всего);
   КонецЦикла;    

У меня получилось 136 бананов

Поправка .. осталось 137 бананов
Учел факт, что если остался один банан - за ним не надо возвращаться

(56) твоя поправка смещает результат до 138

(57) Неа.. банан то мы оставим лежать

Всего=1000;
   Для сч=1 по 100 Цикл
       ОсталосьПеренести=Всего;
       
       Пока Истина Цикл
           //Идем туда
           Если ОсталосьПеренести>100 Тогда
               ОсталосьПеренести=ОсталосьПеренести-100;
               Всего=Всего-1;
           Иначе    
               Всего=Всего-1;
               Прервать;
           КонецЕсли;  
           
           //Надо ли возвращаться
           Если ОсталосьПеренести=1 Тогда
               //Оставляем банан там
               Всего=Всего-1;
               Прервать;
           Иначе
               Всего=Всего-1;
           КонецЕсли;    
       КонецЦикла;    
       
       Сообщить("Километр "+сч+" Осталось"+Всего);
   КонецЦикла;

137

(0)
такое ощущение, что в последнее время объявлен конкурс "кто найдет баян про дремучей"
эта задача - очередной баян, даже на мисте уже была:
Подскажите как протестить програмера 1С7

(61) это же прекрасно

(0) 136 :)?

(0) На 0 километре 1000 бананов.
На 1 километре  981 банан: 9 ходок туда-обратно и одна туда, то есть
1000 - (2*9+1) = 981 банан.
С 1-го по 6 километр на каждом километре теряется 19 бананов.
На 6 километре 1000 - 6*19 = 886
с 6-го по 11 километр на каждом километре теряется 17 бананов.
На 11 километре 896 - 5*17 = 801

Вот тут развилка :). Делаем 7 ходок туда-обратно и одну туда, (один банан оставляем на 11 километре)
801 - (2*7+1) - 1 (оставленный) = 785

Итого, на 12 километре 801 - (2*7+1) - 1 (оставленный) = 785

с 12-го по 18 километр на каждом километре теряется 15 бананов.
На 18 километре 785 - 6*15 = 695
с 18-го по 26 километр на каждом километре теряется 13 бананов.
На 26 километре 695 - 8*13 = 591
с 26-го по 35 километр на каждом километре теряется 11 бананов.
На 35 километре 591 - 9*11 = 492
с 35-го по 46 километр на каждом километре теряется 9 бананов.
На 46 километре 492 - 11*9 = 393
с 46-го по 60 километр на каждом километре теряется 7 бананов.
На 60 километре 393 - 14*7 = 295
с 60-го по 79 километр на каждом километре теряется 5 бананов.
На 79 километре 295 - 19*5 = 200
с 79-го по 100 километр на каждом километре теряется 3 банана.
На 100 километре 200 - 21*3 = 137 бананов

(54) "На 6 километре 1000 - 6*19 = 896" ?

1000 - 6*19 = 886 !

Короче ответ 137 бананов.

(0)810

гоню:(

(66)
А если она будет перетаскивать на 100 м кучи ?

(69) Да. Сейчас думаю о "непрерывной" обезьяне :)

1-й участок: длина 100/19=5,26...  19 ходок - съели 100 бананов, перенесли 900
2-й участок: длина 100/17=5,88..   17 ходок - съели 100 бананов, перенесли 800
3-й участок: длина 100/15=6,67..   15 ходок - съели 100 бананов, перенесли 700
4-й участок: длина 100/13=7,69..   13 ходок - съели 100 бананов, перенесли 600
5-й участок: длина 100/11=9,09..   11 ходок - съели 100 бананов, перенесли 500
6-й участок: длина 100/9 =11,11..   9 ходок -  съели 100 бананов, перенесли 400
7-й участок: длина 100/7=14,29..    7 ходок - съели 100 бананов,  перенесли 300
8-й участок: длина 100/5=20,00      5 ходок - съели 100 бананов,  перенесли 200

дошли до точки 80 км.

затем 3 ходки по 20 км - окончательно перенесем 140 бананов

(0)92

епть опять не то:(

900 бананов останется , 100 отдаст таксисту (таже обезьяна) )))

всего=1000;
   для а=1 по 100 цикл
       если  Цел(всего/100)= всего/100 тогда
           колСот=всего/100;
       иначе
           колСот=Цел(всего/100)+1;
       конецесли;
       сообщить(всего);
       если Всего/100-цел(Всего/100)=0.01 тогда
           всего=всего-(колсот-1)*2+1;
       иначе
           всего=всего-колсот*2+1;
       конецесли;    
   конеццикла;    
   сообщить(всего);

138

Если по километру таскать то 852 съели, 10 бросили на дороге, 138 перенесли

//блин по три км уже сложнее . по 2 км много бананов брасать приходится, 18...

//ставим отделом. можете высылать бананы

(71)точно

(0)Дык концу дня, то скажут правильный ответ? ))
у меня 50 и мне все равно, что у большинства получилось 138-140)

Получилось 138 бананов:
Не уверен, что это максимум, но каждое движение влево обезьяна несёт максимальное число бананов

Dim BananArray(100) ' от 0 до 100 километров
Dim ObezPos ' позиция обезьяны
' начальные условия
For ObezPos=1 To 100 Step 1
   BananArray(ObezPos)=0
Next
ObezPos=0
BananArray(0)=1000

Dim FsoObject
Set FsoObject=WScript.CreateObject("Scripting.FileSystemObject")
Dim LogObject
Set LogObject=FsoObject.CreateTextFile(WScript.ScriptFullName & ".log",True,False)

Dim i
' теперь начинаем перенос
Dim f
f=1 ' движение влево
Do ' бесконечный цикл переноса
   LogObject.Write(CStr(ObezPos))
   For i=0 To 100 Step 1
       LogObject.Write(vbTab & CStr(BananArray(i)))
   Next
   LogObject.WriteLine("")
   If ObezPos=100 Then
       i=0
       For ObezPos=0 To 99 Step 1
           If BananArray(ObezPos)<>0 Then
               i=1
               Exit For
           End If
       Next
       If i=0 Then
           WScript.Echo(BananArray(100))
           Exit Do
       End If
       ObezPos=100 ' восстанавливаем переменную цикла
   End If
   If f=1 Then ' выполняем движение влево
       If ObezPos<100 Then
           i=BananArray(ObezPos) ' взяли все бананы
           If i>100 Then i=100 ' остальные уронили, так как тяжело
           BananArray(ObezPos)=BananArray(ObezPos)-i ' вычисляем, сколько бананов осталось
           ObezPos=ObezPos+1 ' прошли километр
           If i=0 Then
               WScript.Echo("Обезьяна умерла")
               Exit Do
           End If
           i=i-1 ' съели один банан
           If BananArray(ObezPos)=0 Then ' если здесь ничего нет
               BananArray(ObezPos)=i
               f=2 ' переключаемся на движение назад
           Else
               BananArray(ObezPos)=BananArray(ObezPos)+i
           End If
       Else
           f=2 ' тупо сразу идём назад
       End If
   Else ' выполняем движение вправо
       If ObezPos>0 Then
           If BananArray(ObezPos-1)<>0 Then ' если есть за чем спешить
               ObezPos=ObezPos-1
               BananArray(ObezPos)=BananArray(ObezPos)-1 ' едим обратный банан
           Else
               f=1 ' нужно идти назад
           End If
       Else ' двигаться некуда - надо снова влево
           f=1 ' здесь мы делаем пустой цикл без шага
       End If
   End If
Loop
LogObject.Close()
WScript.Echo("Конец")

решение должно быть связано с числом E

пусть в точке 0 Х бананов, тогда при переходе на расстояние др бананов меньше станет Х/100*dr

Х'=-Х/100

Xn=1000*exp(-100/100)=.....

зачем обезьяне ходить по километру, когда можно по 1 метру?

(83) Смысл в том, чтобы нести в нужную сторону как можно больше бананов, то есть не делать ходки, когда она несёт менее 100 бананов.

(84) учел

просто расстояние может быть не кратно километру...

уменьшение расстояния до метра увеличит остатки бананов

(85) А потом она будет таскать неполные кучи (99 и т.д. бананов) - на них "КПД падает" и все бананы съедаются.
Потом, что по метру, что по пол-километра - разницы никакой - будет съедено 10 бананов, на перенос всей кучи - а не факт, что кучу надо нести всю и сразу - будут пронесены те бананы, которые всё равно съедят.

(86) вообще я рассмотрел что затраты на перенос при переносе 10 бананов составляют 1/10 (это упрощение и приближение)

верхняя оценка 367,8

Это в случае буферизующей обезьяны, когда она сначала съедает все необходимые бананы, а потом тащит все оставшиеся.
То есть обезьяна гарантирована должна ходить
Ходов=ОкруглитьВверх(Итог/100)
раз туда и на один раз меньше обратно, то есть всего
(Ходов+Ходов-1)*100 бананов должно быть съедено.
Тогда получаем уравнение:
Итог+(200*ОкруглитьВверх(Итог/100))-100=1000
(Итог/100)+(2*ОкруглитьВверх(Итог/100))=9
Получается, что Итог/100 - целое или Итог=300
То есть максимальная оценка 300, но она недостижима.

Непрерывные и буферизующие обезьяны.. Внушаить!

кстати нетривиальный вариант - стоять на месте и перекидывать бананы в сторону дома :) тогда 900 останется

Помоему в (71) показан оптимальный вариант

интересна квантовая обезьяна

дифур, вроде получается:

У' = у/50 - 1

у(0) = 1000
найти у(100)

почему? У' = у/50 - 1

y=exp(x/50)+1 в твоем случае значит обезьяна собирает бананы по мере движения

не то, что-то http://www.wolframalpha.com/input/?i=dy%2Fdx%3Dy%2F50-1%2C++y(0)%3D1000%2C+x%3D100

http://www.wolframalpha.com/input/?i=dy%2Fdx%3Dy%2F50-1%2C++y(0)%3D1000%2C+x%3D100

(98) тьфу, в общем вводим dy/dx=y/50-1,  y(0)=1000, x=100
получаем y(100) = 50+950 e^2

(99) не правильно что-то

сотня?

dy/dx=1 - y/50 ?

(101) похоже 178,56851907478205729929952022386

у = 950exp(-x/50)+50

x=100, у=178.57

да, нужно брать с минусом - бананы убывают...

Уранение не правильное -
покажите все уравнения оптимизационное задачи

не вижу как перенести больше чем в (71)

оно не дискретное, описывает процесс в целом:

у бананов в точке х

количество поездок в след. точку: у/100
количество ходок: 2*у/100 - 1
на расстояние dx
на расход бананов на км: 1

dy = -(y/50-1)dx

(106)не взлетит - количество поездок в след точку ОКРВВЕРХ(у/100) - полраза не пойдешь, здесь дискретность

(107) см первое предложение.