Programovací hádanka (C#, Visual studio) – C / C++ – Fórum – Programujte.com

Dobrý den, musím vyřešit úkol, s kterým si nevím moc rady. Zní:

Vyřešte úlohu s trpaslíky (Bruteforce, backtracking):
Na jedné straně mostu stojí 4 trpaslíci. Chtějí přejít přes most, ale mají jenom jednu lucerničku. Most unese najednou pouze 2 trpaslíky a trpaslík nemůže jít přes most bez lucerničky.
Každý trpaslík je jinak zdatný, takže přejdou most za 1, 3, 5 a 10 minut. Jakým způsobem přejdou nejrychleji? Cesta přes most trvá vždy tak dlouho, jak jde pomalejší trpaslík.

Priklad:
1. přechod (L:1,3,5,10 P: )
tam 5 + 10 => 10 min
zpět 5 => 5 min
2. přechod (L:1,3,5 P: 10)
tam 3 + 1 => 3 min
zpět 1 => 1 min
3. přechod (L:1,5 P:10,3)
tam 1 + 5 => 5 min
výsledný stav (L: P:1,3,5,10)
celkem 24 minut.... je to nejmíň?

Nenašel by se prosím Vás někdo, kdo by mi poradil, napsal nějaký kód? Každá rada se cení. Předem děkuji za odpovedi.

Podle mě je nejmíň:

lucernu ma vzdycky minutovej a jde nejdrvi s 10 min
vraci se 1 min
jde s 5 min
vraci se 1 min
jde s 3 min
jsou vsichni tam za 20 min

Neumím ti to napsat v cecku a nevim jestli ti to uznaj jako bruteforce a backtracking, ale stači z tech 4 určit toho nejrychlejšího, kterej bude kmitat s jednim tam a sam zpatky, ty ostatni můžeš vybrat už postupně a jen počítat čas... Nemělo by to byt nic těžkého.

ja sem to resil jako ohodnoceni grafu ... pole o 32 promennejch, bitovy operace pro zjisteni kdo je na jaky strane a kde je lucerna
a pak uz jen funkce ktera zjistila jestli je "tah" mezi nejakym cislem na nejake cislo mozny

To filippop : prave ze je nejrychlejsi poslat dva nejrychlejsi, uplne nejrychlejsi se vrati a posle dva nejpomalejsi
a pak se pro nej vrati ten druhej nejrychlejsi ... mas to pak 3+1+10+3+3

Máš pravdu, zatímco já jsem se dostal na 20 minut, ty jsi se dostal na úplně jiných rychlejších 20 minut /.-)

blbe nastaveny.. zkus 1 2 100 150

to ze to vyslo stejne je fakt jen nahoda... ze sou ty hodnoty blbe zadany..

To filippop : Postup, který popsal KIIV je použitelný obecně. Tvůj pouze na tento příklad. Například pokud budou časy trpaslíků 1, 3, 9, 10.
Ty dostaneš: 10 + 1 + 9 + 1 + 3 = 24
KIIV dostane: 3 + 1 + 10 + 3 + 3 = 20

Děkuji všem za své příspěvky.

#9 trumpeta
podekuj radsi za ty jejich

#10 rage
Sláva archeologii! A já myslel, že to upozornění, které tu Curo implementoval, je psáno dost velkým písmem...