Fişierul intrare/ieşire:	pietre2.in, pietre2.out	Sursă	Grigore Moisil 2010, clasa a 9-a
Autor	Clara Ionescu	Adăugată de	Serban Andrei Stan •savim
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Pietre2

În Egiptul antic piramidele s-au construit pe terenuri de formă pătratică. Aceste terenuri au fost împărţite în zone pătratice de latură 1. Pe aceste pătrăţele se aşezau un număr de cuburi de piatră. Atunci când urma să aşeze un cub nou, egiptenii porneau de undeva de la marginea terenului şi avansau astfel încât la fiecare pas să treacă pe un pătrăţel pe care numărul cuburilor de piatră era exact cu 1 mai mare decât numărul pietrelor în locul unde se aflau. Ei nu puteau păşi de pe un anumit pătrat pe altul cu care acesta era vecin în diagonală. Piatra se aşeza pe pătratul de la care nu mai puteau avansa.

Cerinţă

Determinaţi cel mai lung drum pe care îl vor parcurge egiptenii pentru a transporta o piatră la locul ei.

Date de intrare

Pe prima linie a fişierului de intrare pietre2.in se află lungimea n a laturii pătratului pe care se transportă pietrele. Pe fiecare dintre următoarele n linii se află câte n numere naturale, despărţite prin câte un spaţiu, reprezentând numărul cuburilor de piatră aflate pe pătratele corespunzătoare.

Date de ieşire

Pe prima linie a fişierului de ieşire pietre2.out se va scrie un număr natural, reprezentând lungimea celui mai lung drum (numărul paşilor necesari care, pornind dintr-o poziţie oarecare, trecând prin pătrate vecine se poate avansa în sus). Pe cea de a doua linie a fişierului de ieşire se va scrie poziţia de început, precizând indicele de linie şi cel de coloană, separate prin câte un spaţiu. Dacă nu există nicio poziţie de la care să se poată avansa în sus, pe prima linie a fişierului se va scrie numărul 0, iar pe a doua linie se vor scrie două numere egale cu 0.

Restricţii

• 1 ≤ n ≤ 100
• 0 ≤ număr cuburi pe un pătrat ≤ 10 000
• Dacă există mai multe soluţii, se va afişa una singură.

Exemplu

Explicaţie

Pornind din colţul stânga-sus se pot efectua cel mult 5 paşi (1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6). Din orice altă poziţie, drumurile ar fi mai scurte.

Cum se trimit solutii?