| Fişierul intrare/ieşire: | revolutie.in, revolutie.out | Sursă | ONI 2009, clasele 11-12 |
| Autor | Andrei Grigorean | Adăugată de |  Andrei Misarca •Mishu91 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Revolutie
În ţara Utopia a avut loc recent o revoluţie digitală, în urma căreia s-a hotărât să se întrerupă serviciile de telefonie mobilă. Din fericire, Miruna s-a infiltrat în sediul central al principalului furnizor de telefonie din Utopia. Pentru a repune în funcţiune reţeaua, Miruna trebuie să treacă de un filtru de autentificare: ea are în faţă o matrice pătratică de dimensiune N având elemente din mulţimea {0, 1}. Asupra acestei matrice se pot efectua următoarele operaţii:
- se aleg două linii şi se interschimbă;
- se aleg două coloane şi se interschimbă.
Pentru a trece de filtrul de autentificare Miruna trebuie să obţină pe diagonala principală (toate elementele de forma A[i][i]) valori egale cu 1.
Determinaţi pentru Miruna o secvenţă de maxim 4*N operaţii astfel încât să reuşească să treacă de filtrul de autentificare.
Date de intrare
Fişierul de intrare revolutie.in va conţine pe prima linie numărul N, reprezentând dimensiunea matricei. Pe următoarele N linii se află câte N valori din mulţimea {0, 1} reprezentând valorile matricei.
Date de ieşire
Fişierul de ieşire revolutie.out va conţine pe prima linie un singur număr întreg T reprezentând numărul de operaţii efectuate. Fiecare din următoarele T linii va descrie câte o operaţie: primul caracter de pe linie va fi L dacă s-a aplicat o operaţie asupra liniilor şi C dacă s-a aplicat o operaţie asupra coloanelor. Vor urma două valori între 1 şi N reprezentând indicii liniilor/coloanelor interschimbate. În caz că nu există soluţie, se va afişa valoarea -1.
Restricţii
- 1 ≤ N ≤ 127
- Liniile şi coloanele sunt numerotate de la 1 la N
- T trebuie să aparţină intervalului [0, 4*N]
- 30% dintre fişierele de test vor avea 1 ≤ N ≤ 10
- În cazul în care există mai multe soluţii, se va afişa oricare dintre ele
- Miruna se opune fenomenului de “politically correctness”
Exemplu
| revolutie.in | revolutie.out |
|---|---|
| 2 0 1 1 0 | 1 L 1 2 |
Explicaţie
Interschimbând primele două linii obţinem matricea:
1 0
0 1
