Urmașii lui Moisil 2023 - Clasa a IX-a - Mirror | sah

Să considerăm o tablă de șah de dimensiune $n$ ($n$ este par), în care liniile și coloanele sale sunt numerotate de la $1$ la $n$. Pe această tablă se află, pe fiecare pătrat, câte un număr natural astfel încât suma numerelor de pe pătratele albe este egală cu suma numerelor de pe pătratele negre.
Pătratele vecine ale pătratului cu coordonatele $(i, j)$, $1\leq i\leq n$, $1\leq j\leq n$ sunt toate pătratele din lista dată : $(i-1, j)$ , $(i, j-1)$, $(i+1, j)$, $(i, j+1)$ , ale căror coordonate aparțin intervalului $[1,n]$.

Definim două operații:

1. 1 i j k p x – adună la valorile două pătrate vecine aflate pe pozițiile $(i,j)$ și $(k,p)$ același număr natural $x$.
2. 2 i j k p – scade din valorile două pătrate vecine aflate pe pozițiile $(i,j)$ și $(k,p)$ valoarea minimă reținută pe cele două poziții.

Cerință

Utilizând un număr cât mai mic de operații de tip $1$ sau $2$ să se obțină pe tabla de șah numai valori nule.

Date de intrare

Fișierul de intrare sah.in conține pe prima linie numărul natural $n$, iar pe următoarele $n$ linii se găsesc câte $n$ numere naturale reprezentând câte o linie din matrice.

Date de ieșire

Fișierul de ieșire sah.out va conține mai multe linii. Pe fiecare linie este definită câte o operație, deci va conține fie șase numere dacă operația este de tip $1$, fie cinci numere dacă operația este de tip $2$.

Restricții și precizări

• $2 \leq n \leq 100$ și $n$ este par;
• $0 \leq a_{ij} \leq 500$, pentru $1 \leq i, j \leq n$;
• $1 \leq i, j,k,p \leq n$ și $0 \leq |x| < 1 \ 000 \ 000 \ 000$;
• $0\leq a_{ij}\leq 10^{9}$ la orice moment de timp;
• Valorile scrise pe aceeași linie în fișierul de intrare, respectiv în fișierul de ieșire sunt separate prin câte un spațiu.
• Dacă la un test numărul de operații pe care-l obțineți este mai mic decât $n^2$ și operațiile conduc la matricea nulă, atunci veți obține punctajul complet pe acel test.
• Restricțiile precizate sunt pentru fiecare test, punctajul fiind suma punctelor obținute pe fiecare test.
• Valorile scrise pe aceeași linie în fișierul de intrare și în fișierul de ieșire sunt separate prin câte un spațiu.
• Este acceptată orice soluție corectă.
• Veți primi punctaj maxim ($100$% din valoarea testului) dacă numărul de operații pe care-l obțineți este mai mic decât $n^2$;
• Veți primi punctaj parțial ($50$% din valoarea testului) dacă numărul de operații pe care-l obțineți este cuprins între $[n^2, 2 * n^2]$;
• Nu veți primi niciun punctaj ($0$% din valoarea testului) dacă numărul de operații pe care-l obțineți este mai mare decât $2 * n^2$ sau există operații incorecte;

Exemplu

sah.in

2
7 5
3 1

sah.out

1 2 1 2 2 4
2 1 1 2 1
2 1 2 2 2

Explicație

După prima operație matricea devine:

7 5
7 5

După a doua operație matricea devine:

0 5
0 5

După a treia operație matricea devine:

0 0
0 0