Fişierul intrare/ieşire:	polihroniade.in, polihroniade.out	Sursă	OJSEPI 2021, clasele 11-12
Autor	Andrei Constantinescu	Adăugată de	Matteo Verzotti •Matteoalexandru
Timp execuţie pe test	0.375 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Polihroniade

O matrice pătratică de dimensiuni N × N cu N par si elemente din multimea {0, 1} se numeste tablă de sah dacă oricare două celule vecine pe o linie sau pe o coloană au valori diferite (cu alte cuvinte, dacă nu există două valori egale alăturate).

De ziua ei, Victor i-a cumpărat Elisabetei o astfel de matrice A, care nu este neapărat tablă de sah. Aflând despre pasiunea ei, acesta vrea acum să transforme matricea A intr-o tablă de sah. Timpul fiind limitat, el poate efectua doar următoarele tipuri de operatii asupra matricei:

1. Interschimba valorile i si j din A (celelalte linii rămân neschimbate, iar valorile din interiorul liniilor i si j rămân neschimbate si isi păstrează ordinea). Operatia are sens pentru 1 ≤ i, j ≤ N .
2. Interschimbă coloanele i si j din A (celelalte coloane rămân neschimbate, iar valorile din interiorul coloanelor i si j rămân neschimbate si isi păstrează ordinea). Operatia are sens pentru 1 ≤ i, j ≤ N.

Dorind să o impresioneze pe Elisabeta, Victor apelează la voi, programatori renumiti, să il ajutati in a transforma matricea A intr-o tablă de sah. Pentru aceasta, Victor are nevoie de următoarele informatii:

1. Poate fi transformata matricea A in tablă de sah?
2. Care este numărul minim de operatii necesare pentru a duce la indeplinire acest scop?
3. Care ar fi o succesiune de operatii care transformă matricea A intr-o tablă de sah?

In cazul ultimei cerinte, pentru a intra in gratiile lui, Victor va trebui ca numărul de operatii efectuate să fie minim. Totusi, chiar si un număr neminim de operatii va fi răsplătit, insă nu intr-atât de mult.

Vi se dau două numere P, T si T matrice A, reprezentând mai multe instante ale problemei. Pentru fiecare matrice A dintre cele T va trebui să rezolvati cerinta cu numărul P ∈ {1, 2, 3} dintre cele listate mai sus.

Date de intrare

Fişierul de intrare polihroniade.in va contine pe prima linie doua numere intregi pozitive P si T, reprezentând numarul cerintei de rezolvat si, respectiv, numărul de scenarii pentru care va trebui să rezolvat problema.

Urmează cele T instante ale problemei, fiecare fiind compusă din N + 1 linii: pe prima linie se va afla numarul N, iar pe următoarele N linii câte N cifre binare neseparate prin spatii, reprezentând câte o linie a matricei A.

Date de ieşire

În fişierul de ieşire polihroniade.out, pentru fiecare dintre cele T instante se va afisa răspunsul, incepând de la o linie nouă, după cum urmează:

1. Dacă P = 1, atunci se va afisa pe o singură linie 1 dacă matricea A poate fi transformată in tablă de sah, si 0 altfel.
2. Dacă P = 2, atunci se va afisa pe o singură linie un ı̂ntreg reprezentând numărul minim de interschimbări de linii si/sau coloane necesare pentru a transforma matricea A in tablă de sah.
3. Dacă P = 3, atunci se va afisa pe o linie un număr X. Apoi, pe fiecare dintre următoarele X linii se va afisa câte o interschimbare de linii sau coloane, după următorul format: L i j are semnificatia că liniile i si j se interschimbă, iar C i j are semnificatia că coloanele i si j se interschimbă. Matricea obtinută după aplicarea celor X operatii asupra lui A in ordinea dată trebuie să fie o tablă de sah.

Restricţii

• 1 ≤ T ≤ 350
• 1 ≤ N ≤ 1 000
• N este par.
• Pentru cerintele de tip P = 2 si P = 3 se garantează că matricea A poate fi transformată ı̂n tablă de sah folosind interschimbări de linii si/sau coloane.
• Suma valorilor N pentru cele T scenarii nu depăseste 2 000.

Pentru 40 de puncte

• P = 1

Pentru alte 34 de puncte

• P = 2

Pentru alte 26 de puncte

• P = 3
• Dacă există mai multe solutii, oricare este considerată corectă.
• Dacă numărul X de operatii folosite nu este minim, atunci se acordă 50% din punctajul pe test.

Exemple

Explicaţii

Pentru primul exemplu, avem P = 1, deci pentru cele T = 3 instante se cere numai dacă se pot transforma in tablă de sah prin interschimbări de linii si/sau coloane. Pentru prima instantă acest lucru nu este posibil, deoarece nu avem niciun 0 ı̂n matrice. Pentru cea de-a doua instantă, putem efectua următoarele operatii:

s

Cum se trimit solutii?