Soluţii corecte primite de la Zoltan Szabo, Angela Sandu, Aurel Ionescu, Ady Nicolae, Claudiu Emil Man, Sorin Andrei Popovici, Camelia Muşetescu, Cristian Bălănoiu, Ştefan Gaţachiu.
Soluţie parţială: Marin (?)
Am păstrat soluţia lui Zoltan Szabo, mai uşor de redactat în condiţiile de pe site:
A.
2 2 2
4 6 6 6
4 8 4 4
4 8 2 3
Cel mai mic scor este 5 și se trece prin numerele 0 2 2 6 4 2 3 obținând scorurile intermediare și scorul final: 0 2 3 7 7 5 5.
Soluția este unică.
B.
1 2 3
4 3 2 1
1 2 3 4
4 3 2 1
Cel mai mic scor este 3 și se poate obține pe 8 trasee diferite. Pentru indicarea traseelor vom folosi notația J- JOS respectiv D-DREAPTA
1. JJDJDD, se trece prin numerele 0 4 1 2 3 2 1 obținând scorurile intermediare și scorul final: 0 4.2 3 4 4 3
2. DJJJDD, se trece prin numerele 0 1 3 2 3 2 1 obținând scorurile intermediare și scorul final: 0 1 3 3 4 4 3
3. JJDDJD, se trece prin numerele 0 4 1 2 3 2 1 obținând scorurile intermediare și scorul final: 0 4.2 3 4 4 3
4. DJJDJD, se trece prin numerele 0 1 3 2 3 2 1 obținând scorurile intermediare și scorul final: 0 1 3 3 4 4 3
5. DJDJJD, se trece prin numerele 0 1 3 2 3 2 1 obținând scorurile intermediare și scorul final: 0 1 3 3 4 4 3
6. DDJJJD, se trece prin numerele 0 1 2 2 3 2 1 obținând scorurile intermediare și scorul final: 0 1 2 3 4 4 3
7. DJDDJJ, se trece prin numerele 0 1 3 2 1 4 1 obținând scorurile intermediare și scorul final: 0 1 3 3 2 5 3
8. DDJDJJ, se trece prin numerele 0 1 2 2 1 4 1 obținând scorurile intermediare și scorul final: 0 1 2 3 2 5 3
C.
1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Cel mai mic scor este 22 și se trece prin numerele 0 1 2 3 7 11 15 obținând scorurile intermediare și scorul final: 0 1 2 4 9 15 22.
Soluția este unică.
Sorin Andrei Popovici dă o formulă recursivă de rezolvare (programare dinamică):
Smini,j = min(Smini-1,j, Smini,j-1)/2 + vali,j | i,j >= 2
= Smini-1,1/2 + vali,1 | j=1
= Smin1,i-1/2 + val1,i | i=1
Logic
