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