73. Верблюд в пустыне

Ответ...
533 (если учесть, что верблюд выпьет литр на 1000-м километре). Кому интересно решение, могу написать.

Интересен не ответ
А именно Решение.
В частности, доказательство того, что данный ответ -- это действительно Максимальное количество из возможного.

igar
Где же ваше решение?
У меня больше 500 никак не получается :-(

500 - максимум

Решение
Верблюд берёт 1000 л. и проходит 200 км. (точка А), у него осталось 800, он оставляет в т. А 600 л, и идёт назад, оставив себе 200 л., чтобы вернуться. Вернувшись, снова берёт 1000 и относит к т. А 600 л. и снова возвращается за последними 1000 л., и снова дует к т. А, на этот раз приносит 800 л. (не нужно назад идти). Итого в т. А 600+600+800=2000 л.

продолжение...
Верблюд, находясь в т. А, берёт 1000 л. воды, и проходит 333 км. (точка Б), оставляет здесь 334 л, и у него остаётся 333, чтобы вернуться в т. А. Вернувшись в т. А, он забирает оставшиеся 1000 л. и идёт к т. Б, выпивая 333 л., т.е. принесёт он в т. Б 667 л. Итого в т. Б 334+667=1001 л. воды.
т. Б - это 200+333=533 км. Верблюд берёт 1000 и идёт к пункту назначения, пройдя 1000-533=467 км. и выпив 467 л. воды. Итого принесёт он 1000-467=533 л.

1001-467=534 л.

Это не решение.
Это просто вариант ответа.
Докажите, что ваш ответ -- максимально возможный, вот тогда это будет решение.

Обоснование
Решение уже приведено выше, приведу лишь логику рассуждений.

Очевидно, что принести в город больше 1000 л. верблюд не сможет в принципе. Очевидно также, что путь придется делить на n этапов. Следовательно, оставлять больше 1000 литров перед последним n-ным этапом попросту нет смысла - все что сверх 1000 придется там и оставить, ибо возвращаться за ней будет накладно; А оставлять меньше 1000 - невыгодно, т.к. верблюд получается недоиспользован. Следовательно, к началу n-ного этапа там должно находиться ровно 1000 литров воды. Рассуждая аналогичным образом для всех n-1, n-2 и т.д. этапов, получаем, что а) этапов должно быть всего три, т.к. воды изначально 3000 литров, при этом на каждом этапе должно тратиться ровно 1000 литров, кроме последнего этапа; б) протяженность каждого этапа должна быть различной, причем протяженность первых этапов - меньше, т.к. по ним придется сделать больше рейсов.

На самом первом этапе верблюду придется возвращаться за водой дважды, следовательно всего он сделает 5 рейсов на этом этапе (туда-обратно дважды и еще один раз туда). Следовательно, протяженность первого этапа должна составить 1000/5 = 200 км. На втором этапе исходное количество воды не будет превышать 2000 литров, следовательно за водой придется возвращаться лишь один раз, сделав 3 рейса (туда-обратно и снова туда), следовательно, протяженность второго этапа должна составлять 1000/3=333 км, т.к. к началу третьего этапа больше 1000 литров оставлять бесполезно. Протяженность третьего этапа чисто арифметически составляет 467 км. Таким образом, максимальное число воды - 533 литра.

не совсем в тему…
Если верблюд может, стоя на месте, передвинуть всю воду хотя бы на сантиметр, он сможет пройти 1000 км только один раз, донеся 2000 л воды.

перенесет он 1000 л так как он сможет пронести лишь эту массу
но он все это выпьет к концу пути

Ребятки, тут 5 возможных решений...
Но точно 533, так-как расстояние на литры не делится.
1)Здесь возможен ответ 2200 Так как на пути к городу верблюду обязательно встретятся, какие-то кустики, встречи с животными и насекомыми.
2)Может быть самый просто обычный ответ 2000, потому-что всего у него на пути 3000 л, на себе он может нести 1000, а вот у себе в горбых кучу 2000л. Так как каждый км. 1 л. Именно по этому 3000-1000=2000л
3) Я не буду обсуждать ещё ответы которые у меня вышли. Но они такие 1000л, 1300л, 1333,4 л. Залезти в биографию верблюды, и стань те на время ещейка.. Изучайте каждую малую подробность, биографии. Как в своё время это делал Шерлок Холмс, выслеживайте и давайте свои ответы.

Ответ в общем дан, как и решение. Уточню: 533 + 1/3 литров притащит верблюд в город
Cледующая 1000 литров, при цене 3 л/км потратится через 333 + 1/3 км. Итого он пройдёт 200 (за 5 л/км) + 333 + 1/3 (за 3 л/км) и ему останется пройти 466 + 2/3 км, тратя 1 литр на км. Следовательно, двинувшись с последней тысячей, он притащит в город 533 + 1/3 литра.

Уточню: (см. решение igar) до т.А 200 км, от т.А до т.Б 333 км, от старта до т.Б 200+333=533 км.
В т.Б соберется воды 334+667= 1001 л. От т.Б до города 1000-533= 467 км.
Верблюд в город доставит 1001-467=534 л. И никаких дробей.

Уточню: т.к. по условию он не может брать воды более 1000 л, на последнем этапе придется пожертвовать одним литром, и доставить воды 533 л.

интересно
Я поняла, что у верблюда уже есть 3000 л воды и он может на себе нести еще 1000 л воды, соотвественно через 1000 км он придет до нужной ему точки с 3000 л воды

возникла свежая идея, ответ 750 л
Пока даю наводку, если не получится додуматься самостоятельно, то дам решение. Что если, верблюд по дороге на каждый километр будет "скидывать" по несколько литров, тогда на протяжении этого пути он сможет нести 1000л и пить ту воду, которую заранее оставил.
Удачи в размышлениях :)

SegeyASh прав, 533,(3) литра.
werty, от того, что если будем скидывать по несколько литров по пути для возврата, ничего не изменится, т.к. верблюд все равно будет пить столько сколько положено и до 200 километра верблюд будет возвращаться два раза, после 200 и до 533,(3) км один раз в лучшем случае.

В данном случае "донести побольше" тождественно "израсходовать поменьше", а для этого нужно нести груз с умом, стараясь удерживать затраты воды на максимально низкой отметке. Наименьший расход воды — 1 л / 1 км. Он возможен только в случае, если груза у верблюда не более 1000 кг(то есть 1000 литров воды). При превышении лимита расход возрастает по формуле x+2. Потому, при старте, имея 3000 литров(иначе говоря дважды превысив лимит груза), верблюд расходует
5 л / 1 км, так как ему необходимо возвращаться обратно аж два раза. Тогда, при переносе 3000 л на 200 км, при условии, что груз будет
делиться на три части по 1000 л, и таким образом переноситься, верблюд выпьет ту самую 1000 л и следовательно, с этого момента можно весь оставшийся груз брать в два захода, а не в три. Потому, нести 3000 л сразу на расстояние больше 200 км не эффективно, так как после 200 км, верблюд всё ещё будет нести груз тремя частями,
а не двумя, и будет сохранять расход 5 л / 1 км. Итак, мы прошли 200 км, и у нас осталось 2000 л, расход стал 3 л / 1 км. Очевидно, понизить его можно будет лишь когда запасы воды понизятся до 1000 л. Через 333 км у верблюда останется ~ 1000 литров воды. Далее расход составит 1 л / 1 км. В таком случае верблюд доставит в город 533 литра воды
(Это если считать 1 литр неделимой единицей измерения), так как до города 467 км, а у него 1000 литров. Если оставлять воду в пустыне или изначально брать меньше воды для уменьшения расхода, то это
хотя и приведёт к понижению расхода воды, но приведёт и к уменьшению самих её запасов, потому точно не поможет доставить больше. Тоже самое и в обратную сторону: если мы будем нести груз дальше отметок снижения затратности(200 км и 533 км) не уменьшая количество частей груза, то затраты возрастут. Следовательно, иные алгоритмы не эффективны. Значит этот — оптимальный и 533 литра воды — максимум, чего можно добиться.
что можно доставить в город.

555.(5)

Так, нет, неправильно

Пока не понял особо эту задачу , но вот вам просто вариант где больше всего из предложенного сохранится воды, проходим с 1000 л. 333,(3) км. , остается 666,(6) км. и 666,(6) л.,оставляем 333,(3) л., идем обратно, берем еще 1000 л., доходим , скидываем еще 333,(3) л., идем обратно, берем еще 1000 л., приходим и в итоге у нас 333,(3)*2 + 666,(6) = 1332 л. и надо пройти еще 666,(6) км., проходим, остается еще 666,(6) л. , как то так, хотя глубинный смысл задачи пока еще не понял, поэтому доказать что это максимум не могу, да и хз , он ли это.

Ошибся, каюсь.

400 литров
Точка А — 400 км
2 раза оставляет по 200 литров.
В третий раз уверблюда в этой точке 1000 литров. За остальные 600 км до города
расход 600 литров. Принесет 400 л.

См. предыдущие комментарии. Наверное 533 как-то больше, чем 400.

Для решения задачи заметим, что наиболее оптимальный вариант доставки воды достигается при полной начальной загрузки верблюда (отправляющегося в сторону пункта назначения от какой-либо точки на пути) и минимального количества возвратов за водой. Также заметим, что себестоимость подвоза воды к конкретной точке (естественно, при соблюдении полноты начальной загрузки верблюда) не зависит от дробления этого пути (от одной точки до другой точки) на какие-либо дополнительные внутренние отрезки. Поэтому нам необходимо разделить весь путь на соответствующие отрезки так, чтобы расстояние от одной точки отрезка до другой верблюд проходил бы с полной начальной загрузкой и минимальной себестоимостью (т.е. как можно меньше совершал бы возвратов за водой). Поэтому при названных выше условиях изначально верблюд должен возвратиться за водой 2 раза, затем 1 раз и, наконец, оставшийся путь до пункта назначения он преодолевает с полной начальной (от конкретной точки) загрузкой. Условие о минимальном возврате начинает обеспечиваться в момент, когда в какое-то точке остается 2000 л. воды – именно в этом случае достаточно будет только 1 возврата. Нетрудно заметить, что эта точка (допустим, точка «А») находится в 200 км. от начала пути. Затем, чтобы последним (третьим) этапом из соответствующей точки (допустим, точка «В») максимально загруженный верблюд направился без остановок в конечный пункт, нам необходимо, чтобы в этой отправной точки верблюд загрузился бы 1000 л. воды. Значит, из точки «А» в точку «В» верблюд должен перевести 1000л. воды (2000 л. – 1000 л.) на как можно бОльшее расстояние, «потратив» на это еще 1000 л. воды. Последнее достигается только в одном случае – когда верблюд перевозит 1000 л. воды на 333 км. Таким образом, в конечный пункт верблюд перевезет 533 л. (1000 л. — (1000 км. – 200км. – 333 км.)).