Fişierul intrare/ieşire:caroiaj.in, caroiaj.outSursăConcursul National de Informatica "Adolescent Grigore Moisil"
AutorPatrick SavaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test1.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Caroiaj

Serban si Teodora joaca un joc pe o tabla patratica cu N x N celule. Pe fiecare celula a tablei este cate un jeton colorat cu un numar scris pe el, astfel incat, tabla privita de sus, arata precum un caroiaj. O mutare consta in alegerea unui jeton de pe una din cele 2 * N - 1 diagonale principale, daca de pe acea diagonala nu a mai fost ales pana la momentul mutarii niciun alt jeton. Incepe jocul. Cei doi muta alternativ.
Bunicul, amintindu-si ca cei doi vor participa la Concursul National de Informatica "Adolescent Grigore Moisil", ii motiveaza pe cei doi sa lucreze in echipa, astfel incat la finalul celor 2 * N - 1 mutari, sa fi fost alese jetoane diferite(considerand jetoanele alese de Serban si Teodora). Doua jetoane se considera diferite daca numerele de pe ele difera.

Sa se spuna pentru T caroiaje daca cei doi pot muta astfel incat la final toate jetoanele sa fie diferite. In cazul in care exista solutie, sa se afiseze si o modalitate de alegere.

Date de intrare

Fişierul de intrare caroiaj.in va contine pe prima linie un numar natural T, reprezentand numarul de caroiaje. Pe urmatoarea linie se afla un numar natural N, reprezentand latura caroiajului. Urmatoarele N linii contin N numere, linia i + 1 reprezentand cea de-a i-a linie a caroiajului. Aceasta configuratie se repeta de T ori.

Date de ieşire

În fişierul de ieşire caroiaj.out vor fi T linii. Cea de-a i-a linie reprezinta raspunsul pentru testul i. Daca exista solutie, se va afisa mesajul "DA", urmat de 2 * N - 1 numere, reprezentand numerele alese de pe fiecare diagonala in parte. Prima diagonala principala se considera a fi coltul stanga-jos al caroiajului, iar ultima diagonala principala se considera a fi coltul dreapta-sus al caroiajului. In cazul in care pentru testul i nu exista solutie, atunci linia i va contine mesajul "Bunicul este dezamagit!".

Restricţii

  • Pentru toate testele de la evaluare, T = 44.
  • 1 ≤ N ≤ 300.
  • Numerele din matrice sunt cuprinse intre 1 si 109.
  • In cazul in care exista solutie, numerele corespunzatoare jetoanelor alese se vor afisa in ordinea crescatoare a diagonalelor principale pe care sunt pozitionate.
  • Daca exista mai multe solutii, se poate afisa oricare.

Exemplu

caroiaj.incaroiaj.out
1
3
1 2 3
4 5 6
7 8 9
DA 7 4 1 2 3

Explicaţie

Avem matricea

1 2 3
4 5 6
7 8 9

De pe diagonala principala cu numarul de ordine 1 Teodora alege jetonul cu numarul 7
De pe diagonala principala cu numarul de ordine 2 Serban alege jetonul cu numarul 4
De pe diagonala principala cu numarul de ordine 3 Teodora alege jetonul cu numarul 1
De pe diagonala principala cu numarul de ordine 4 Serban alege jetonul cu numarul 2
De pe diagonala principala cu numarul de ordine 5 Teodora alege jetonul cu numarul 3

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?