Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | caroiaj.in, caroiaj.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" |
| Autor | Patrick Sava | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.7 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
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 = 15.
- N <= 300.
- Numerele din matrice sunt cuprinse intre 1 si 10^9.
- In cazul in care exista solutie, numerele corespunzatoare jetoanelor alese se vor afisa in ordinea crescatoare a diagonalelor principale pe care sunt pozitionate.
Exemplu
| caroiaj.in | caroiaj.out |
|---|---|
| 1 3 1 2 3 4 5 6 7 8 9 | DA 7 4 1 2 6 |
Explicaţie
Avem matricea
1 2 3
4 5 6
7 8 9
De pe diagonala principala cu numarul de ordine 1 alegem jetonul cu numarul 7
De pe diagonala principala cu numarul de ordine 2 alegem jetonul cu numarul 4
De pe diagonala principala cu numarul de ordine 3 alegem jetonul cu numarul 1
De pe diagonala principala cu numarul de ordine 4 alegem jetonul cu numarul 2
De pe diagonala principala cu numarul de ordine 5 alegem jetonul cu numarul 6
