Revolutie

revolutie

== include(page="template/taskheader" task_id="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.
 

Poveste şi cerinţă...

h2. 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.
 

Fişierul de intrare $revolutie.in$ ...

h2. 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$.

În fişierul de ieşire $revolutie.out$ ...

h2. 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”

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. revolutie.in |_. revolutie.out |

| 2
0 1
1 0
| 1
L 1 2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Interschimbând primele două linii obţinem matricea:
$1 0$
$0 1$

...
 

== include(page="template/taskfooter" task_id="revolutie") ==

3931