Am primit soluţii corecte de la Zoltan Szabo, Lucian Niţă, Angela Sandu, Aurel Ionescu, Marian Baloo, Irina Spânu, Camelia Muşetescu, Dan Florescu, Emil Claudiu Man, Viorel Manta, Cristian Bălănoiu.
Toţi au găsit o traversare în 29 secunde.
Dau soluţia lui Zoltan Szabo, care cuprinde şi o generalizare:
Pasul 1. 3 secunde
traverseaza 1+3 (1,3)
Pasul 2. 1 secunda
revine 1 (3)
Pasul 3. 12 secunde
traverseaza 8+12 (3,8,12)
Pasul 4. 3 secunde
revine 3 (8,12)
Pasul 5. 6 secunde
traverseaza 1+6 (1,6,8,12)
Pasul 6. 1 secunda
revine 1 (6,8,12)
Pasul 7. 3 secunde
traverseaza 1+3 (1,3,6,8,12)
Timpul necesar parcugerii podului: 3+1+12+3+6+1+3=29 de secunde
Generalizare:
N persoane vor să traverseze un pod. Timpii de traversare pentru fiecare persoană în ordine crescătoare sunt următoarele t1 ≤ t2 ≤ t3 ≤ t4 ≤... ≤ tN-1 ≤ tN. Podul fiind şubred, nu pot trece mai mult de două persoane. În plus, este noapte, şi au o singură lanternă la dispoziţie... Să se calculeze timpul minim necesar traversării podului.
Rezolvare:
Dacă N=1 persoana traverseaza direct în timp t1.
Dacă N=2 persoanele traverseaza direct în timp t2.
Dacă N=3, timpul minim este t1+t2+t3 şi se obţine astfel: prima dată vor trece 1 şi 3 îu timpul t3, apoi 1 se întoarce în timp t1 iar în final 1 şi 2 vor trece în timp t2.
Dacă N=4, în funcţie de valorile ti , 1≤i≤4 alegem una din două variante de traversare:
varianta a.
1. trece 1 şi 2 în timp t2,
2. revine 1 în timp t1,
3. trece 1 şi 3 în timp t3,
4. revine 1 în timp t1,
5. trece 1 şi 4 în timp t4,
Timpul total de traversare este 2t1+t2+t3+t4
varianta b.
1. trece 1 şi 2 în timp t2,
2. revine 1 în timp t1,
3. trece 3 şi 4 în timp t4,
4. revine 2 în timp t2,
5. trece 1 şi 2 în timp t2,
Timpul total de traversare este t1+3t2+t4
Comparăm duratele de timp pentru cele două variante, studiind în ce condiţii este mai avantajoasă varianta a doua:
t1+3t2+t4 < 2t1+t2+t3+t4 sau după reducerea termenilor 2t2 < t1+t3
Deci dacă 2t2 < t1+t3, vom alege varianta 2, altfel alegem varianta 1 pentru traversare.
Observaţie: în caz de egalitate 2t2 = t1+t3, ambele variante de traversare vor da acelaşi rezultat de timp.
Dacă N=5, în funcţie de valorile ti , 1≤i≤5.
Vom proceda ca la n=4 pentru persoanele t1, t2, t4, t5. Adică dacă 2t2 < t1+t4 se alege varianta cu timpul de traversare t1+3t2+t5
1. trece 1 şi 2 în timp t2,
2. revine 1 în timp t1,
3. trece 4 şi 5 în timp t5,
4. revine 2 în timp t2,
5. trece 1 şi 2 în timp t2,
În caz contrar (2t2 > t1+t4, cazul de egalitate admite ambele variante de rezolvare), timpul de traversare va fi 2t1+t2+t4+t5
1. trece 1 şi 2 în timp t2,
2. revine 1 în timp t1,
3. trece 1 şi 4 în timp t4,
4. revine 1 în timp t1,
5. trece 1 şi 5 în timp t5,
În continuare
6. revine 1 în timp t1
7. trece 1 şi 3 în timp t3.
Timpul necesar pentru paşii 6 şi 7 este t1+t3. Totalul timpului parcurs va fi min(2t1+3t2+t3+t5,3t1+t2+t3+t4+t5)
În cazul general, când N>5, avem în vedere următoarele proprietăţi ştiind că timpii de execuţie sunt în ordine crescătoare t1 ≤ t2 ≤ t3 ≤ t4 ≤... ≤ tN-1 ≤ tN
Algoritmul se prezintă în felul următor:
Fie şirul timpilor de traversare t1, t2, t3, t4,... tN-1, tN
În acest şir c