Задача 140.041 (Хамър-ът на Слави)

Скоро попаднах на една задача, която ме впечатли със простото си условие и сложността на решението. Не мога да се стърпя и да не я споделя с вас:



Както знаете Слави разигра Хамър-а си и 10 000 л. безплатен бензин по Коледа. Ако си представим, че вие сте го спечелили и:

1. Хамър-ът изразходва по 100 л. бензин на 100 км.

2. Резервоарът му събира точно 100 л. (няма никакъв резервен обем).

3. Можете да натоварите само един допълнителен резервоар от 100 л. гориво.

4. Десетте хиляди литра гориво са разфасовани в 100 допълнителни резервоара.

5. Вие се намирате в изходен пункт с пълен резервоар (бонус) и склад със 100-те допълнителни пълни резервоара.



На какво максимално разстояние от изходния пункт можете да се отдалечите?







В задачата няма уловки. Можете сами да си товарите и разтоварвате допълнителните резервоари. Можете да пресипвате произволно от един в друг резервоар. Ако искате си представете, че сте в пустинята и можете да се движите по идеално права линия и т.н.

<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">**************На какво максимално разстояние от изходния пункт можете да се отдалечите?

*********************

<div align="right">Originally posted by pimpirlit*-*13/01/2005*:* 16:37:59</div id="right">

</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">



по въпроса - макс. 10 000 км.





иначе реално - маск. на 2 м от табелата СОФИЯ ( ако си късметлия може и само с леко отупване да минеш )

Идеята е следната. Взимаш един допълнителен, караш го на 50 км, оставяш го и се връщаш, пълниш и взимаш един и така докато в изходната точка е Хамара и един резервоар. Зареждаш и отижаш до точка едно където има 50 резервоара и в хамара има половинка. По същата схема се предживаш на още 50 км и там има вече 24. 150-11.5->200-5->250-2.5->450 и остава половин резервоар на последната база. Не съм сигурен дали е оптимално решение но идеята трябва да е нещо такова.

Да, това е идеята. Но това е очевидното, но далеч не оптималното решение. Пътя за решаване е оптимизирането на разстоянията между пит-стоповете. Пример с три резервоара:



По твоя начин ще изминем 250 км.



Ако направим пит-стоп не на 50 км., а на 66 2/3 км. от началото, свалим допълнителния резервоар. Отлеем от него 33 1/3 л. в основния => ще имаме 66 2/3 л. в основния и ще можем да се върнем в изходния пункт. Там пълним догоре основния и товарим последния допълнителен. Тръгваме пак и на пит-стопа ще имаме 33 1/3 л. останали в основния и пълен допълнителен. Допълваме основния от оставения преди това допълнителен (в него, след отливането имаме останали 66 2/3 л.) и продължаваме още 200 км. => общо 266 2/3 км., т.е. със 16 2/3 км. повече!

Но... лесно е с три резервоара. Със 100+1 на мен ми се връзва погледа на фльонга [V].

За отговора на задачата не знам, но не сещам за коментарите на собствениците на различни коли в автомобилен форум.



Хъмър:

- - - Днес катастрофирах. 24 ранени, 10 убити.

Трябва ли да взема черната боя от официалния вносител?

До там са 25 километра. Това са си 35 лева за бензин.



То май това беше пускано тука цялото... [:D]

@pimpirlit,

Може да не съм разбрала какво казваш, но с 3 варела, ако пит-стопът е на 50 км от началния пункт, можем да се отдалечим на 200 км (не на 250), а, ако пит-стопа е на 2/3 от началото - само на 166,66 км. Причината е, че в първия случай сме прахосали 1 резервоар, отивайки до пит-стопа и връщайки се, а във втория - 4/3 резервоар е похабен. Грешката ти е, че казваш 3, а използваш 4 варела (зареждаш първия, товариш втория, връщаш се, зареждаш третия и какво товариш? четвърти!).

Ако искаме да стигнем по-далече, трябва да минимизираме дължината на тези тропоски напред-назад, така мисля.



//EDIT

Сега виждам, че за 200 км ни стигат и два варела.

Ако (в случая с 3 варела) сложим пит-стопа на 1/3 от базата, ще постигнем по-добър резултат. Когато се върнем при него (носейки последния) ще сме изразходвали само един резервоар, а ще имаме два пълни и ще минем 233,33 км общо. Съмнявам се, че това може да се подобри.

@Bibi,

Ти си разбрала точно. Аз не съм го написал пълно - в примера имах предвид 3 допълнителни резервоара. Забравил съм да напиша, че си има и пълен собствен. Извинявам се за недоглеждането, но в края на работния ден мисля и пиша... Целта беше да се излюстрира принципа на оптимизация. Мисля, че и идеята да се започне оптимизацията отзад напред е по-добрата.



BTW задачката е за собствено удоволствие (нормалните хора ще кажат, че си е чист мазохизъм). Моята информация за най-добро решение (може би) е 560 км. 800 и нещо метра с 57 пит-стопа! За съжаление го нямам, а не съм се доближил много до него[:(]

@pimpirlit,

Би ли ми казал колко гориво имаме по условие?

101 резервоара (100 в хангара и един в Хамъра) или общо 100?

Ако са общо 100, мога да ти кажа как да изминеш малко повече от 500 км., а ако са 101 не знам още точно колко. Но цяла нощ местя варели и вече имам мускулна треска, та би ли ми доизяснил, да не се мъча излишно?

@Bibi,

101 резервоара - 100 допълнителни и един в самия Хамър, т.е. пълния пробег на колата е 10100 км. (в условието не съм сбъркал този път [:)])

Може да се покаже, че теоретичния максимум за отдалечаване е 588,5 км., но като не се вземат предвид ограниченията.

А по модифициран метод на Yasen6275 може да се стигне до малко над 510 км. (дано не съм сбъркал пак, ще го проверя отново).

Успех!

<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">@Bibi,

101 резервоара - 100 допълнителни и един в самия Хамър, т.е. пълния пробег на колата е 10100 км. (в условието не съм сбъркал този път [:)])

Може да се покаже, че теоретичния максимум за отдалечаване е 588,5 км., но като не се вземат предвид ограниченията.

А по модифициран метод на Yasen6275 може да се стигне до малко над 510 км. (дано не съм сбъркал пак, ще го проверя отново).

Успех!



<div align="right">Originally posted by pimpirlit*-*14/01/2005*:* 19:44:33</div id="right">

</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">



Предполагам имаш предвид това решение:

My answer is 510.8749 miles



There are altogether 101 tanks of petrol.



1st checkpoint: 100/199 miles from start, you can transport 100 tanks of petrol here, but 1 tankful petrol is consumed.



2nd checkpoint: 50 miles from the 1st checkpoint.

You will have 50.5 tanks of petrol left.



3rd checkpoint: 100/198 miles from the 2nd checkpoint.

That is to use the half tank of petrol to transport 50 tanks of petrol to 3rd checkpoint. So 50 tanks left.



4th checkpoint: 50 miles from the 3rd checkpoint.

You will have 25.5 tanks of petrol left.



5th checkpoint: 100/98 miles from the 4th checkpoint.

That is to use the half tank of petrol to transport 25 tanks of petrol to 5th checkpoint. So 25 tanks left.



Keep going and you'll eventually get 13 checkpoints altogether.



6th checkpoint: 100/47 miles more and 24 tanks left.

7th checkpoint: 50 miles more and 12.5 tanks left.

8th checkpoint: 100/46 miles more and 12 tanks left.

9th checkpoint: 50 miles more and 6.5 tanks left.

10th checkpoint: 100/22 miles more and 6 tanks left.

11th checkpoint: 50 miles more and 3.5 tanks left.

12th checkpoint: 50 miles more and 2 tanks left.

13th checkpoint: 200 miles more and 0 tanks left.



Add up the total and you get:

500+100/199+100/198+100/98+100/47+100/46+100/22=510.8749 miles



Съжалявам, че е на английски, но от една страна не ми се превежда, от друга - не искам някой да помисли, че претендирам сам да съм открил решението.

Ето какво решение (по-скоро метод) предлага човек, който твърди, че най-далечното разстояние е 560,754 км. Същия човек е дал и решението 588,5 км, което за жалост е чисто теоретично (предвижда оставяне и пълнене на повече от 100 л):



Първото ми прозрение беше, че ефикасността на решението се определя от пълното разстояние, което камионът може да измине. Придвижвайки се напред, имате все по-малко гориво,съответно и по-малко пътувания м/у две "бази". На първия етап от пътя имате гориво за 10100 км и можете да изминете не повече от 200 км наведнъж. Следователно трябва да потегляте (тук авторът има предвид потегляне с пълен резервоар от някоя от базите) не по-малко от 51 пъти. В същото време, изминавайки първите 2 км от маршрута си след тези 51 потегляния, сте изгорили 102 л гориво. Така имате 9998 л на разположение. Това означава, че, ако първата база е на 2 км от изходната точка, не може да потеглите от нея повече от 50 пъти и да превозите всичкото гориво.



Това е основата за всяко възможно решение. Ако разгледате диаграмата позиция-време, ще получите диаграми, подобни на приложените.



http://www.ocf.berkeley.edu/~wwu/YaB...fuel_tanks.gif



Първото откритие, което направих, беше, че последната база е на 66 2/3 км от предишната. Това е лесно да се изчисли: искате последния етап от пътуването да започне с гориво за 200 км (пълен резервоар и резерва). Пътуването до последната база започва два пъти с по 200 литра. Искате да изгорите точно 200 литра, пътувайки общо три пъти м/у базите. Следователно трябва да пропътувате 66 2/3 км, да оставите 66 2/3 л, да се върнете, да вземете 200 л, да отидете отново до последната база, да заредите и да продължите пътуването с 200 л. Това перфектното оптимално решение (особено ако започвате с 3 варела гориво).



След опитване на много методи забелязах, че да работя от финала към началото на пътуването е единствения начин да постигам успех. По същия начин открих разстоянието м/у предпоследната и последната база. До/от нея пътуваме общо 5 пъти, използвайки 200 л гориво. Следователно тя трябва да е на 40 км от предходната. Би трябвало да пропътуваме 40 км, да оставим 120 л гориво и да се върнем с останалите 40 л. Проблемът е, че не можем да оставим 120 л (един варел побира 100 л). Както е показано на диаграмата, трябва да зареждаме 3 пъти на предпоследната база. Тъй като можем да оставим там не повече от 100 л, следователно не можем да зареждаме с повече от 33 1/3 л, което ни кара да поставим предпоследната база на 33 1/3 км от базата преди нея (пред-предпоследната).



Пресмятанията за пред-предпоследната (ПП) база довеждат до следващите усложнения. Използвайки същите пресмятания, както и за предпоследната база, би трябвало да приемем разстоянието да предишната база за 20 км. Всъщност няма нужда да зареждаме 5 пъти. Забележете, че при първото връщане от предпоследната база ще имаме 33 1/3 л излишно гориво. Така че няма нужда да зареждаме след първите две пътувания м/у ПП база и предходната. Уравнението, което решаваме тук е 5х = 133 1/3 (1 резервоар, който можем да оставим и 33 1/3 л излишно гориво). Това ни дава разстояние от 26 2/3 км от ПП база до предходната. По подобен начин може да се изчисли разстоянието до всяка предходна база.



Приятно смятане. Аз, каквото можах, направих.