Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | aleatoare.in, aleatoare.out | Sursă | Algoritmiada 2022, Runda 3 |
| Autor | Alexandru Petrescu | Adăugată de |  Alexandru Petrescu •alexpetrescu |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Matrice Aleatoare
Marcel a dat peste o matrice patratica de latura N pe care o stie doar el. In ea sunt scrise toate numerele de la 1 la N2. El ia fiecare linie si ii scrie numerele in ordine aleatoare pe cate o foaie (o foaie pt fiecare linie). Procedeaza asemanator si cu coloanele (cate o foaie pt fiecare coloana). Apoi amesteca foile intre ele (nu mai stim, pentru o foaie, nici macar daca e linie sau coloana). Ymüsnı primeste aceste 2N foi si trebuie sa reconstituie matricea initiala. In caz ca sunt mai multe solutii, Marcel indrageste principiile energiei minime in univers asa ca isi doreste matricea minima din punct de vedere lexicografic (se considera sirul obtinut prin concatenarea liniilor - fiecare la dreapta precedentei).
Colegul sau francez, LeCram, isi pune o intrebarea putin mai... sérieuse. Vrea sa schimbe (daca e nevoie) foile lui Marcel in asa fel incat matricea pe care i-o returneaza Ymüsnı sa fie cat mai mare posibil din punct de vedere lexicografic. LeCram se intreaba care este aceasta matrice maxima lexicografic.
Cerinte
Prima cerinta este sa il ajutati pe Ymüsnı sa reconstituie matricea initiala. A doua cerinta este sa ii raspundeti lui LeCram cu matricea maxima lexicografic pe care ar putea-o construi Ymüsnı in vreun context.
Date de intrare
Fişierul de intrare aleatoare.in contine, pe prima linie, numerele C (cerinta: poate fi 1 sau 2) si T (numarul de teste). Pe liniile urmatoare sunt descrise cele T teste: Daca C = 1, mai intai apare numarul N iar pe urmatoarele 2N linii; Fiecare din aceste linii descrie cate o foaie, prin cate N numere. Daca C = 2, apare doar numarul N, deoarece foile date de Marcel nu mai conteaza, LeCram ii poate da orice foi vrea.
Date de ieşire
În fişierul de ieşire aleatoare.out se afla, indiferent de cerinta, T matrici, descrise prin cate N linii cu cate N numere. Atunci cand C = 1, matricea afisata este cea gasita de Ymüsnı care sa corespunda foilor primite. Atunci cand C = 2, matricea afisata este cea gasita tot de Ymüsnı, doar ca in cazul in care LeCram i-ar da foile in asa fel incat rezultatul sa fie maxim lexicografic.
Restricţii
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 50
- Se garanteaza ca, pentru datele de test, reconstituirea realizata de Ymüsnı este posibila, adica nu sunt greseli in foi
- Pentru evaluare, se vor folosi 10 teste. Testele cu indice par vor avea C = 2, iar cele impare vor avea C = 1
- Pentru primele 2 teste, garantam ca 1 ≤ N ≤ 10
- Pentru urmatoarele 2 teste, garantam ca 11 ≤ N ≤ 20
- Pentru urmatoarele 2 teste, garantam ca 21 ≤ N ≤ 30
- Pentru urmatoarele 2 teste, garantam ca 31 ≤ N ≤ 40
- Pentru ultimele 2 teste, garantam ca 41 ≤ N ≤ 50
Exemplu
| aleatoare.in | aleatoare.out |
|---|---|
| 1 2 3 4 9 3 3 5 2 8 2 1 6 7 5 7 4 8 6 1 9 4 3 2 5 9 3 7 6 1 16 8 1 4 13 6 14 10 15 16 10 5 2 14 8 11 13 9 4 12 11 15 12 7 | 1 2 8 6 5 7 9 3 4 1 3 6 7 4 9 13 12 8 2 14 11 16 5 10 15 |
| 2 2 2 1 | 1 3 4 2 1 |
Explicaţie
In al doilea exemplu, primul test, LeCram ii poate da foile: [3, 1], [3, 2], [4, 1], [2, 4]
