Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

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

Верблюд должен пройти через пустыню к ближайшему городу, который располагается на расстоянии 1,000 км. В начале пути он располагает 3,000 литров воды, однако может на себе нести не более 1,000. За каждый километр пройденного пути он выпивает один литр воды. Верблюд может оставлять воду в пустыне и потом забирать её.

Вопрос: Какое максимально количество воды он может перенести в город?
2008-08-28

Обсуждение


Задачи :: Верблюд в пустыне
↓↓ 0 ↑↑   Zero (38 / 335)   29 авг 2008 17:05   »»


Ответ...
533 (если учесть, что верблюд выпьет литр на 1000-м километре). Кому интересно решение, могу написать.
↓↓ 0 ↑↑   igar (10 / 119)   13 сен 2007 13:06   «« #2 »»   Ответить


Интересен не ответ
А именно Решение.
В частности, доказательство того, что данный ответ -- это действительно Максимальное количество из возможного.
↓↓ 0 ↑↑   eruditor (128 / 439)   13 сен 2007 14:15   «« #3 »»   Ответить


igar
Где же ваше решение?
У меня больше 500 никак не получается :-(
↓↓ 0 ↑↑   Zero (38 / 335)   15 сен 2007 18:49   «« #4 »»   Ответить


500 - максимум
↓↓ 0 ↑↑   lemoren (4 / 14)   15 сен 2007 20:31   «« #5 »»   Ответить


Решение
Верблюд берёт 1000 л. и проходит 200 км. (точка А), у него осталось 800, он оставляет в т. А 600 л, и идёт назад, оставив себе 200 л., чтобы вернуться. Вернувшись, снова берёт 1000 и относит к т. А 600 л. и снова возвращается за последними 1000 л., и снова дует к т. А, на этот раз приносит 800 л. (не нужно назад идти). Итого в т. А 600+600+800=2000 л.
↓↓ 0 ↑↑   igar (10 / 119)   17 сен 2007 11:36   «« #6 »»   Ответить


продолжение...
Верблюд, находясь в т. А, берёт 1000 л. воды, и проходит 333 км. (точка Б), оставляет здесь 334 л, и у него остаётся 333, чтобы вернуться в т. А. Вернувшись в т. А, он забирает оставшиеся 1000 л. и идёт к т. Б, выпивая 333 л., т.е. принесёт он в т. Б 667 л. Итого в т. Б 334+667=1001 л. воды.
т. Б - это 200+333=533 км. Верблюд берёт 1000 и идёт к пункту назначения, пройдя 1000-533=467 км. и выпив 467 л. воды. Итого принесёт он 1000-467=533 л.
↓↓ 0 ↑↑   igar (10 / 119)   17 сен 2007 11:46   «« #7 »»   Ответить


Это не решение.
Это просто вариант ответа.
Докажите, что ваш ответ -- максимально возможный, вот тогда это будет решение.
↓↓ 0 ↑↑   eruditor (128 / 439)   18 сен 2007 11:20   «« #8 »»   Ответить


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

Очевидно, что принести в город больше 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 литра.
↓↓ 0 ↑↑   dimka (0 / 12)   05 окт 2008 16:31   «« #9 »»   Ответить


не совсем в тему…
Если верблюд может, стоя на месте, передвинуть всю воду хотя бы на сантиметр, он сможет пройти 1000 км только один раз, донеся 2000 л воды.
↓↓ 0 ↑↑   d1ma (0 / 7)   15 май 2009 11:20   «« #10 »»   Ответить


перенесет он 1000 л так как он сможет пронести лишь эту массу
но он все это выпьет к концу пути
↓↓ 0 ↑↑   toro (-4 / 16)   09 мар 2010 20:35   «« #11 »»   Ответить


Ребятки, тут 5 возможных решений...
Но точно 533, так-как расстояние на литры не делится.
1)Здесь возможен ответ 2200 Так как на пути к городу верблюду обязательно встретятся, какие-то кустики, встречи с животными и насекомыми.
2)Может быть самый просто обычный ответ 2000, потому-что всего у него на пути 3000 л, на себе он может нести 1000, а вот у себе в горбых кучу 2000л. Так как каждый км. 1 л. Именно по этому 3000-1000=2000л
3) Я не буду обсуждать ещё ответы которые у меня вышли. Но они такие 1000л, 1300л, 1333,4 л. Залезти в биографию верблюды, и стань те на время ещейка.. Изучайте каждую малую подробность, биографии. Как в своё время это делал Шерлок Холмс, выслеживайте и давайте свои ответы.
↓↓ 0 ↑↑   QWE321654 (0 / 17)   13 авг 2010 21:46   «« #12 »»   Ответить


Ответ в общем дан, как и решение. Уточню: 533 + 1/3 литров притащит верблюд в город
Cледующая 1000 литров, при цене 3 л/км потратится через 333 + 1/3 км. Итого он пройдёт 200 (за 5 л/км) + 333 + 1/3 (за 3 л/км) и ему останется пройти 466 + 2/3 км, тратя 1 литр на км. Следовательно, двинувшись с последней тысячей, он притащит в город 533 + 1/3 литра.
↓↓ 0 ↑↑   SergeyASh (4 / 36)   27 ноя 2010 11:29   «« #13 »»   Ответить


интересно
Я поняла, что у верблюда уже есть 3000 л воды и он может на себе нести еще 1000 л воды, соотвественно через 1000 км он придет до нужной ему точки с 3000 л воды
↓↓ 0 ↑↑   Lasto4ka (0 / 8)   01 апр 2011 16:58   «« #14 »»   Ответить


возникла свежая идея, ответ 750 л
Пока даю наводку, если не получится додуматься самостоятельно, то дам решение. Что если, верблюд по дороге на каждый километр будет "скидывать" по несколько литров, тогда на протяжении этого пути он сможет нести 1000л и пить ту воду, которую заранее оставил.
Удачи в размышлениях :)
↓↓ 0 ↑↑   werty (0 / 1)   15 апр 2011 19:57   «« #15 »»   Ответить


SegeyASh прав, 533,(3) литра.
werty, от того, что если будем скидывать по несколько литров по пути для возврата, ничего не изменится, т.к. верблюд все равно будет пить столько сколько положено и до 200 километра верблюд будет возвращаться два раза, после 200 и до 533,(3) км один раз в лучшем случае.
↓↓ 0 ↑↑   Андрей (3 / 9)   25 мар 2013 14:40   «« #16 »»   Ответить


В данном случае "донести побольше" тождественно "израсходовать поменьше", а для этого нужно нести груз с умом, стараясь удерживать затраты воды на максимально низкой отметке. Наименьший расход воды — 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 литра воды — максимум, чего можно добиться.
что можно доставить в город.
↓↓ 0 ↑↑   Гидон (0 / 19)   07 апр 2016 14:21   «« #17 »»   Ответить


555.(5)
↓↓ 0 ↑↑   SverkunovEN (0 / 2)   20 июл 2016 00:00   «« #18 »»   Ответить


Так, нет, неправильно
↓↓ 0 ↑↑   SverkunovEN (0 / 2)   20 июл 2016 00:41   «« #19 »»   Ответить


Пока не понял особо эту задачу , но вот вам просто вариант где больше всего из предложенного сохранится воды, проходим с 1000 л. 333,(3) км. , остается 666,(6) км. и 666,(6) л.,оставляем 333,(3) л., идем обратно, берем еще 1000 л., доходим , скидываем еще 333,(3) л., идем обратно, берем еще 1000 л., приходим и в итоге у нас 333,(3)*2 + 666,(6) = 1332 л. и надо пройти еще 666,(6) км., проходим, остается еще 666,(6) л. , как то так, хотя глубинный смысл задачи пока еще не понял, поэтому доказать что это максимум не могу, да и хз , он ли это.
↓↓ 0 ↑↑   Марк Мурадян (0 / 10)   05 сен 2016 18:34   «« #20 »»   Ответить


Ошибся, каюсь.
↓↓ 0 ↑↑   Марк Мурадян (0 / 10)   05 сен 2016 19:08   «« #21 »»   Ответить


400 литров
Точка А — 400 км
2 раза оставляет по 200 литров.
В третий раз уверблюда в этой точке 1000 литров. За остальные 600 км до города
расход 600 литров. Принесет 400 л.
↓↓ 0 ↑↑   АЛЕКСАНДР (0 / 6)   01 июн 2017 06:30   «« #22   Ответить



Ваше имя
Email
Текст ответа
© 2006-2017   Авторы