Fișierul intrare/ieșire	cub.in, cub.out	Sursă	Olimpiada locala 2010, clasele 11-12
Autor	Dan Grigoriu	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	1

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Cub

Un cub are latura de n unități și este împărțit în n³ cuburi elementare de latură 1. Fiecare cubuleț elementar are asociat un număr de puncte. Numerotarea cubulețelor elementare se face cu indicii:

• i, arată etajul (nivelul): 1 pentru cel de sus și n pentru cel de jos, cele n etaje fiind obținute prin secționarea cubului cu n-1 plane echidistante paralele cu fețele sus-jos ale cubului;
• j, arată “felia” verticală astfel: 1 pentru cea din spate și n pentru cea din față, cele n “felii” fiind obținute prin secționarea cubului cu n-1 plane echidistante paralele cu fețele față-spate ale cubului;
• k, arată “felia” verticală astfel: 1 pentru cea din stânga și n pentru cea din dreapta, cele n “felii” fiind obținute prin secționarea cubului cu n-1 plane echidistante paralele cu fețele stînga-dreapta ale cubului.

Fiecărui cub elementar i se asociază un punctaj exprimat printr-o valoare naturală cel mutl egală cu 10.

Un mobil se află pe poziția (1, 1, 1), adică sus, în spate și în stânga și trebuie să ajungă în poziția (n, n, n), adică jos, în față și în dreapta. El se poate deplasa doar în direcțiile: sus, jos, stânga, dreapta, față și spate.

Drumul trebuie sa fie de lungime minimă (număr minim de pași) și în aceste condiții el trebuie să acumuleze un număr maxim de puncte, culegând tot punctajul cubulețelor prin care trece, inclusiv pozițiile (1, 1, 1) și (n, n, n).

Cerințe:

• Să se afle puntajul maxim ce se poate obține în aceste condiții.
• Să se precizeze pozițiile elementare prin care trece drumul corect care a fost ales.

Date de intrare

Fișierul de intrare cub.in conține:

• Numerele n și m separate cu un spațiu pe prima linie: n este dimensiunea cubului și m este numărul de poziții elementare ce conțin un punctaj strict pozitiv, celelalte poziții având punctajul 0.
• Pe următoarele m linii: câte 4 numere naturale, primele 3 reprezentând câte o poziție (i, j, k) și al patrulea fiind punctajul asociat acelei poziții; cele 4 numere se separă cu câte un spațiu.

Date de ieșire

Fișierul de ieșire cub.out conține:

• Numărul maxim de puncte culese pe drumul ales, pe prima linie
• Pe următoarele linii se trec pozițiile drumului ales (prin cele trei coordonate separate de câte un spațiu), începând cu (1, 1, 1) și până la (n, n, n).

Restricții

• 1 ≤ n ≤ 20
• 0 ≤ m ≤ n³
• Punctajul asociat unei poziții elementare are valori naturale de la 0 la 10
• Pot fi mai multe variante de drum ce respectă condițiile; se cere doar o soluție.
• Se va acorda 60% din punctaj pentru determinarea corecta a punctajului maxim si 100% din punctaj pentru rezolvarea corecta a ambelor cerinte

Exemplu