Fişierul intrare/ieşire:	suma3.in, suma3.out	Sursă	Grigore Moisil 2008, clasa a 9-a
Autor	Clara Ionescu, Csaba Patcas	Adăugată de	Filip Cristian Buruiana •filipb
Timp execuţie pe test	0.075 sec	Limită de memorie	4736 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Suma3

Pe o foaie cu patratele avem delimitat un dreptunghi. Pe fiecare patratel din interiorul dreptunghiului delimitat este scris un singur numar natural. Exact jumatate din numere sunt egale cu 0, iar restul numerelor sunt distincte. Ne propunem sa cream un traseu pe caroiajul din interiorul dreptunghiului parcurgand toate numerele diferite de 0 astfel incat pe traseu fiecare numar sa apara o singura data. Parcurgerea numerelor se realizeaza trecand de la un numar la unul dintre numerele cu care se invecineaza in caroiaj pe linie, pe coloana sau pe diagonala. Definim suma traseului ca fiind egala cu suma produselor de forma k * a_i,j, unde k este numarul de ordine al numarului in ordinea parcurgerii, iar a_i,j este numarul curent in traseu.

Cerinta

Determinati traseul avand suma minima, precum si aceasta suma.

Date de intrare

Pe prima linie a fisierului de intrare suma3.in se afla doua numere naturale, M si N, reprezentand dimensiunile dreptunghiului (acesta va avea M linii si N coloane). Pe urmatoarele M linii sunt scrise cate N numere naturale separate prin cel putin un spatiu.

Date de iesire

Pe prima linie a fisierului de iesire suma3.out se va scrie un numar natural, reprezentand suma traseului minim. Pe a doua linie se va descrie traseul minim, adica toate numerele diferite de 0 din caroiaj, in ordinea in care au fost introduse in suma. Numerele se vor separa prin cel putin un spatiu.

Restrictii

• 1 ≤ M, N ≤ 8
• M * N va fi intotdeauna numar par
• 0 ≤ nr_i,j ≤ 100, pentru orice i intre 1 si M, j intre 1 si N
• Intotdeauna va fi posibil sa se parcurga toate numerele

Exemplu

Explicatie

1 * 10 + 2 * 8 + 3 * 2 + 4 * 3 + 5 * 4 + 6 * 1 = 10 + 16 + 6 + 12 + 20 + 6 = 70.

Cum se trimit solutii?