Drumuri

Fie $N$ un număr natural şi $A$ un şir indexat de la $1$, cu $N^2$ elemente, ce constituie o permutare a numerelor $1$, $2$, $3$, . . . , $N^2$. Dintr-o poziţie $i$, cu $1 \leq i \leq N^2$, ne putem deplasa în poziţia:

• $i − 1$, dacă $i − 1$ nu se divide cu $N$
• $i + 1$, dacă $i$ nu se divide cu $N$
• $i − N$ , dacă $i-N \geq 1$
• $i + N$ , dacă $i+N \leq N^2$

Un element $A_i$ se numeşte start dacă toate elementele în care ne putem deplasa din poziţia $i$ au valoarea mai mare decât $A_i$. Un drum este o succesiune de elemente, $A_{i_1}, A_{i_2}, . . . , A_{i_k}$, cu $k \geq 1$, astfel încât $A_{i_1} < A_{i_2} < . . . < A_{i_k}$, cu proprietatea că elementul $A_{i_1}$ este start şi că ne putem deplasa din poziţia $i_1$ în $i_2$, din $i_2$ în $i_3$,..., din $i_{k-1}$ în $i_k$.

Cerință

Să se afişeze un şir $A$ astfel încât numărul drumurilor să fie cât mai mic (şi să nu depăşească $10^9$), precum şi numărul drumurilor din şirul afişat.

Date de intrare

Fişierul de intrare drumuri.in conține pe prima linie numărul natural $N$.

Date de ieșire

Fişierul de ieşire drumuri.out va conține pe prima linie $N^2$ numere naturale distincte cuprinse între $1$ și $N^2$, separate prin câte un spațiu, reprezentând elementele şirului $A$. Pe a doua linie va fi scris numărul drumurilor din şirul $A$ scris pe prima linie.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$
• Numărul drumurilor din şirul $A$, notat $nrdrum$, trebuie să fie mai mic decât $1 \ 000 \ 000 \ 000$.
• Dacă numărul drumurilor este corect determinat pentru şirul $A$ afişat, se acordă $40 \%$ din punctaj.
• În plus, se acordă $(\frac{nrmin}{nrdrum})^4 \cdot 60 \%$ din punctaj, unde $nrmin$ este numărul minim de drumuri care se poate obţine pentru o permutare a şirului $1$, $2$, $3$, . . . , $N^2$, dacă studiem toate permutările posibile.

Exemplul 1

drumuri.in

2 

drumuri.out

1 2 3 4
5

Explicație

Pentru primul exemplu drumurile sunt $(1)$, $(1, 2)$, $(1, 2, 4)$, $(1, 3)$, $(1, 3, 4)$, iar cum $5$ este numărul minim de drumuri pentru toate permutările şirului $1$, $2$, $3$, $4$, se vor acorda $100$ de puncte.

Exemplul 2

drumuri.in

2

drumuri.out

1 3 4 2
6

Explicație

Pentru al doilea exemplu drumurile sunt $(1)$, $(1, 3)$, $(1, 4)$, $(2)$, $(2, 3)$, $(2, 4)$ şi se vor acorda $40 + (\frac{5}{6})^4 \cdot 60 = 68.93$ puncte.

Exemplul 3

drumuri.in

3

drumuri.out

7 6 9 1 3 5 4 8 2
15

Explicație

Pentru al treilea exemplu drumurile sunt $(1)$, $(1, 4)$, $(1, 4, 8)$, $(1, 3)$, $(1, 3, 5)$, $(1, 3, 5, 9)$, $(1, 3, 6)$, $(1, 3, 6, 7)$, $(1, 3, 8)$, $(1, 7)$, $(1, 3, 6, 9)$, $(2)$, $(2, 5)$, $(2, 5, 9)$, $(2, 8)$ şi se vor acorda $73.85$ puncte.