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

This was the problem page during the contest. Access the current page here.
Time limit: 0.1s Memory limit: 128MB Input: sah.in Output: sah.out

Să considerăm o tablă de șah de dimensiune nn (nn este par), în care liniile și coloanele sale sunt numerotate de la 11 la nn. 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)(i, j), 1in1\leq i\leq n, 1jn1\leq j\leq n sunt toate pătratele din lista dată : (i1,j)(i-1, j) , (i,j1)(i, j-1), (i+1,j)(i+1, j), (i,j+1)(i, j+1) , ale căror coordonate aparțin intervalului [1,n][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,j) și (k,p)(k,p) același număr natural xx.
  2. 2 i j k p – scade din valorile două pătrate vecine aflate pe pozițiile (i,j)(i,j) și (k,p)(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 11 sau 22 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 nn, iar pe următoarele nn linii se găsesc câte nn 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 11, fie cinci numere dacă operația este de tip 22.

Restricții și precizări

  • 2n1002 \leq n \leq 100 și nn este par;
  • 0aij5000 \leq a_{ij} \leq 500, pentru 1i,jn1 \leq i, j \leq n;
  • 1i,j,k,pn1 \leq i, j,k,p \leq n și 0x<1 000 000 0000 \leq |x| < 1 \ 000 \ 000 \ 000;
  • 0aij1090\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 n2n^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 (100100% din valoarea testului) dacă numărul de operații pe care-l obțineți este mai mic decât n2n^2;
  • Veți primi punctaj parțial (5050% din valoarea testului) dacă numărul de operații pe care-l obțineți este cuprins între [n2,2n2][n^2, 2 * n^2];
  • Nu veți primi niciun punctaj (00% din valoarea testului) dacă numărul de operații pe care-l obțineți este mai mare decât 2n22 * 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

Log in or sign up to be able to send submissions!