Intelektuāls jautājums IX
Šis ir vienkāršs loģisks uzdevums, parasti šādus uzdod mācoties lineārās programmēšanas uzdevumus, lai gan viegli risinās arī izmantojot domāšanu.
Tātad:
Četriem vīriem naktī jāšķērso tilts. Tilts ir vecs un pussabrucis un vienlaicīgi spēj turēt tikai divus cilvēkus, tiltam nav arī margas, toties vīriem ir viens kabatas lukturītis. Katrā šķērsošanas reizē, vienalga vai šķērso viens vai divi cilvēki, līdzi ir jānes lukturītis. Kabatas batereja ir jānodod no rokas rokā, tas ir to nedrīkst pārmest, bet jāpārnes pāri tiltam. Katrs vīrs pārvietojas ar dažādu ātrumu:
1. vīrs var šķērsot tiltu 1 minūtē;
2. vīrs var šķērsot tiltu 2 minūtēs;
3. vīrs var šķērsot tiltu 5 minūtēs;
4. vīrs var šķērsot tiltu 10 minūtēs;
Ja iet divi vīri kopā, tad tilta šķērsošanas ātrums ir vienāds ar lēnākā gājēja ātrumu.
Piemēram, ja šķērso 1. un 4. vīrs, tad tilts tiek šķērsots 10 minūtēs.
Visi vīri atrodas vienā tilta pusē.
Kāds ir ātrākais iespējamais laiks, lai visi vīri šķērsotu tiltu?
Papildus:
Uzdevumā nav nekādas slēptas „Fiškas”, vīri nedrīkst stiept viens otru uz muguras, kabatas lukturītis nav tik spēcīgs, lai izgaismotu tiltu visā garumā, nevienam nav līdzi nostiepjams šņoris, neviens nemāk levitēt utt.
Comments
19 min.
aha, man arī sanāca 19 min …. tipa tas ātrākais stiepj lukturi atpakaļ ?
Bet var vēl ātrāk 😉
Nu gan tu stāsti…
Man dators ar pilno pārlasi (visus cilvēkus bīdīja šurpu turpu pāri tiltam visos iespējamos veidos) atrada precīzi 19 minūtes kā ātrāko laiku.
Reku kods: http://paste.php.lv/6394 (Python’ā)
Reku viena no atbildēm: 1+ 2,1,5+1,1,10+1 (kārtība kādā cilvēki iet pāri tiltam – vispirms 1 2 turp, tad 1 atpakaļ, pēc tam 5 1 turp, 1 atpakaļ un beigās 10 1 turp).
Reku visas iespējamās kombinācijas: http://paste.php.lv/6395 Nav tur mazāk minūšu par 19.
Ātrāk var vienīgi, ja visi iet bez luktura, pa diviem pāri, tad ir min(10,5) min(2,1)=12 minūtes 🙂 Kam vispār tas lukturis tur vajadzīgs?
Forši, wordpress atkal visas plus zīmes apēda.
Bubu cepuri nost, tu esi makan paņēmies!!! Lukturis vajadzīgs, lai no bezmargu tilta nenokristu.
Tev tas kods visus variantus tomēr neapskata, taču, ja tu piemēram savu variantu #9 nedaudz nomodificētu, tad redzētu, ka var ātrāk 🙂
Kur nu maktan paņēmies.. prasīja ne vairāk kā 5 minūtes (pie tam vēl lieku darbu izdarīju – to done mainīgo nemaz nevajag 😉
Mana programma apskata visus iespējamos variantus. Jekburu variantu nedaudz “modificējot” tu iegūsi citu no tā visa garā saraksta. Tagad pamanīju, ka tur pat ir daži lieki varianti – piemirsu, ka nevajag apskatīt gadījumus, kuri ņem vērā kurš cilvēks no tiem abiem diviem iet pa priekšu 🙂 tb i j ir tas pats, kas j i.
Man liekas, ka gļuku programmā nav. Citu variantu vienkārši nav, ja esmu sapratis uzdevumu pareizi.
Varu mēģināt pierādīt, ka nevar mazāk par 19 minūtēm. Katram no 2,5,10-minūšu cilvēkiem ir jāiet vienreiz pāri tiltam (turp vai arī atpakaļ) tādējādi, ka viņš būs tas lēnākais. Tātad ir 2 5 10 = 17 minūtes, kā minimums! Ātrākais cilvēks, kas var atnest atpakaļ to lukturi ir 1-nieka cilvēks. Tas ir jādara vismaz divas reizes – tātad 17 2 = 19 ir minimālais laiks. Jebkurš cits, ja nesīs atpakaļ, tikai paildzinās šo laiku. Nav ļoti formāli, bet ir man tas liekās pietiekoši intuitīvi.
Ā vēl vienu variantu iedomājos – 4.cilvēks ir akls un viņam ir liels pofig par lukturīti – viņš beigās iet viens pats pa tumsu, tad sanāk mazāk – 2 1 5 10 = 18 min 🙂
Labi, bubu došu pareizo atbildi minimālais ir 17 minūtes 🙂 Un tas ir iespējams divos variantos, kuru tava proga izlaiž nezinu gan kāpēc.
Tavs pierādījums par 19 minūtēm nav slikts, arī domāju ka 19 ir maksimums, kamēr nieiedzinu vienādojumu sistēmu solverī.
Ai jopcig. Stulbs esmu. Tiko kolēģis darbā parādīja man gļuku programmā – tā vienmēr pieņēma, ka atpakaļ lukturi nes viens no tikko pārgājušiem cilvēkiem. Bet otrajā reizē tur tak stāv arī kāds cits!
1+2, 1, 5+10, 2, 1+2 = 2+1+10+2+2 = 17 min…
kods: http://pastebin.com/m608d2231 (paste.php.lv nestrādā patlaban kautkas..)
varianti: http://pastebin.com/m560e3a4b
Malacis! Nu redz tagad man nemaz nebūs pareizā atbilde jāraksta.
labs uzd. :))