Fişierul intrare/ieşire:	alge.in, alge.out	Sursă	OLI 2009, Bucuresti, clasele 11-12
Autor	Dan Grigoriu	Adăugată de	Andrei-Bogdan Antonescu •andrei-alpha
Timp execuţie pe test	0.05 sec	Limită de memorie	4736 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Alge

Un acvariu de forma cubică şi latură n se secţionează, mai întâi, cu n-1 plane orizontale şi echidistante, obţinându-se n niveluri de grosime 1, numerotate de la 1 la n ($1$ pentru cel de sus), apoi se secţionează cu n-1 plane verticale echidistante şi paralele cu feţele laterale stânga-dreapta obţinându-se n lame de grosime 1, numerotate de la 1 la n ( 1 pentru cea din stânga), iar la final se secţionează cu n-1 plane verticale, echidistante şi paralele cu feţele laterale faţă-spate, obţinându-se n lame de grosime 1, numerotate de la 1 la n ( 1 pentru cea din faţă). Coordonatele unui cub cu latura 1 din secţiune sunt în ordine: prima coordonată pentru nivel, a doua pentru lama stânga-dreapta şi a treia pentru lama faţă-spate. În acvariu se găsesc ng grupuri de alge. Grupurile au forma cubică, fiind situate în cuburi cu latura 1 din secţiune, şi sunt dispuse astfel încât să nu se atingă între ele, nici măcar printr-un vârf de algă.

Cerinta

Să se determine un drum în acvariu pentru un peştişor, care trebuie să plece din cubul de secţiune situat în colţul stânga-faţă-sus, de coordonate (1;1;1), şi să ajungă în cubul de secţiune situat colţul dreapta-spate-jos, de coordonate (n;n;n), fără să treacă prin niciun grup de alge, iar drumul să fie de lungime minimă.

Date de intrare

Fişierul alge.in conţine pe prima linie cele două numere naturale n şi ng, separate de printr-un spaţiu. Pe fiecare din următoarele ng linii, sunt scrise câte 3 numere naturale, separate prin câte un spaţiu, reprezentând cele 3 coordonate cubului cu latura 1 din secţiune în care este situat un grup de alge. 

Date de ieşire

În fişierul alge.out se vor scrie:

• pe prima linie un număr natural k reprezentând lungimea drumului minim
• pe fiecare dintre următoarele k linii sunt scrise câte trei numere naturale, separate prin câte un spaţiu, reprezentând coordonatele cuburilor cu latura 1 din secţiune prin care trece drumul de lungime minimă (fiecare triplet reprezintă coordonatele unei poziţii în drumul peştişorului (prima poziţie va fi (1;1;1) iar ultima (n;n;n))).

Restricţii

• 2 ≤ n ≤ 35
• 0 ≤ ng ≤ 30
• Cuburile, cu latura 1 din secţiune, situate în colţurile stânga-faţă-sus şi dreapta-spate-jos nu sunt ocupate de alge. 
• Lungimea drumului este egală cu numărul de cuburi cu latura 1 din secţiune prin care trece peştişorul
• Pot exista mai multe drumuri de lungime minimă; se cere o singură soluţie.

Exemplu

Explicaţie

Acvariul are latura de 3 şi există un singur grup de alge situat în cubul cu latura 2 din secţiune de coordonate (3;1;1), adica este lipit de colţul faţă-stânga-jos al acvariului.
Drumul de lungime minimă al peştisorului trece prin k=7 cuburi cu latura 1 din secţiune, şi anume: din cubul de coordonate (1;1;1), în linie dreapta spre spatele acvariului, până în cubul de coordonate (1;1;3), apoi la dreapta spre cubul de coordonate (1;3;3) şi apoi în jos, până în cubul de coordonate (3;3;3).

Cum se trimit solutii?