Rezolvare PBinfo #4374

La grădinița din orașul Matrix, copiii se joacă folosind matrici pătratice în loc de mașinuțe sau păpuși. Axel, fiind un copil foarte bun la informatică, s-a gândit să le propună colegilor un joc cel puțin interesant.
Acesta le oferă un număr natural N și apoi o matrice cu N linii şi N coloane, numerotate de la 1 la N. Matricea conţine numere naturale nenule. Asupra matricei se poate aplica un singur tip de operație, de oricâte ori:

• Se alege un număr i, cuprins între 1 şi N;
• Se permută circular în sus cu o poziţie elementele coloanei i.

De exemplu:

Axel le spune colegilor “Efectuând un anumit număr de operații, putem obţine pe diagonala principală același număr? Puteţi răspunde cu DA sau NU. Dacă răspunsul este DA, atunci determinaţi şi eficienţa transformării, ca fiind diferenţa maximă dintre numărul obţinut pe diagonala principală şi numărul minim de operații efectuate pentru a obţine acest număr.”

Cerința

Deoarece colegii lui Axel sunt totuși prea mici pentru a ști să rezolve astfel de probleme, aceștia vă cer ajutorul și vă roagă să rezolvați problema, oferindu-vă în schimb 100 de puncte.

Date de intrare

Fișierul de intrare axel.in conţine pe prima linie numărul natural N. Pe următoarele N linii se află câte N numere naturale nenule separate prin câte un spaţiu, reprezentând elementele matricei.

Date de ieșire

Fișierul de ieșire axel.out va conține pe prima linie mesajul DA, în cazul în care se poate obține același număr pe diagonala principală sau mesajul NU, în caz contrar. Dacă pe prima linie a fost afișat DA, atunci pe cea de a doua linie a fişierului va fi scris un număr întreg reprezentând eficienţa.

Restricții și precizări

• 1 ≤ N ≤ 1500
• Elementele matricei sunt numere naturale nenule ≤ 8000.

Exemplul 1:

axel.in

4
6 2 2 2
3 6 5 6
2 7 3 7
5 3 6 3

axel.out

DA
3

Explicație

Este optim să aducem numărul 6 pe diagonala principală. Astfel, vom efectua o operație pe coloana 3 și două operații pe coloana 4. Numărul total de operații este 3, deci răspunsul va fi 6 – 3 = 3.

Exemplul 2:

axel.in

5
17 18 15 16 15
11 14 11 15 11
14 12 12 11 13
15 13 14 13 12
12 15 13 14 14

axel.out

DA
10

Exemplul 3:

axel.in

4
1 2 3 4
3 4 1 2
4 1 2 3
5 6 7 8

axel.out

NU

Exemplul 4:

axel.in

4
1 1 1 1
3 4 5 6
7 8 9 2
3 9 7 5

axel.out

DA
-5