Fişierul intrare/ieşire:polihroniade.in, polihroniade.outSursăOJSEPI 2021, clasele 11-12
AutorAndrei ConstantinescuAdăugată deMatteoalexandruMatteo Verzotti Matteoalexandru
Timp execuţie pe test0.75 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Polihroniade

O matrice pătratică de dimensiuni N × N cu N par şi elemente din mulţimea {0, 1} se numeşte tablă de şah 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 şah. Aflând despre pasiunea ei, acesta vrea acum să transforme matricea A într-o tablă de şah. Timpul fiind limitat, el poate efectua doar următoarele tipuri de operaţii asupra matricei:

  1. Interschimbă liniile i şi j din A (celelalte linii rămân neschimbate, iar valorile din interiorul liniilor i şi j rămân neschimbate şi îşi păstrează ordinea). Operaţia are sens pentru 1 ≤ i, j ≤ N .
  2. Interschimbă coloanele i şi j din A (celelalte coloane rămân neschimbate, iar valorile din interiorul coloanelor i şi j rămân neschimbate şi îşi păstrează ordinea). Operaţia are sens pentru 1 ≤ i, j ≤ N.

Dorind să o impresioneze pe Elisabeta, Victor apelează la voi, programatori renumiţi, să îl ajutaţi în a transforma matricea A într-o tablă de şah. Pentru aceasta, Victor are nevoie de următoarele informaţii:

  1. Poate fi transformată matricea A în tablă de şah?
  2. Care este numărul minim de operaţii necesare pentru a duce la îndeplinire acest scop?
  3. Care ar fi o succesiune de operaţii care transformă matricea A într-o tablă de şah?

În cazul ultimei cerinţe, pentru a intra în gratiile lui, Victor va trebui ca numărul de operaţii efectuate să fie minim. Totuşi, chiar şi un număr neminim de operaţii va fi răsplătit, însă nu într-atât de mult.

Vi se dau două numere P, T şi T matrice A, reprezentând mai multe instanţe ale problemei. Pentru fiecare matrice A dintre cele T va trebui să rezolvaţi cerinţa cu numărul P ∈ {1, 2, 3} dintre cele listate mai sus.

Date de intrare

Fişierul de intrare polihroniade.in va conţine pe prima linie două numere întregi pozitive P şi T, reprezentând numărul cerinţei de rezolvat şi, respectiv, numărul de scenarii pentru care va trebui să rezolvaţi problema.

Urmează cele T instanţe ale problemei, fiecare fiind compusă din N + 1 linii: pe prima linie se va afla numărul N, iar pe următoarele N linii câte N cifre binare neseparate prin spaţii, 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 instanţe se va afişa răspunsul, începând de la o linie nouă, după cum urmează:

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

Restricţii

  • 1 ≤ T ≤ 350
  • 1 ≤ N ≤ 1 000
  • N este par.
  • Pentru cerinţele de tip P = 2 şi P = 3 se garantează că matricea A poate fi transformată ı̂n tablă de şah folosind interschimbări de linii şi/sau coloane.
  • Suma valorilor N pentru cele T scenarii nu depăşeşte 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 soluţii, oricare este considerată corectă.
  • Dacă numărul X de operaţii folosite nu este minim, atunci se acordă 50% din punctajul pe test.

Exemple

polihroniade.inpolihroniade.out
1 3
2
11
11
4
1100
1100
0011
0011
2
10
01
0
1
1
2 2
4
1100
1100
0011
0011
2
10
01
2
0
3 2
4
1100
1100
0011
0011
2
10
01
3
L 2 4
C 2 3
L 1 2
0

Explicaţii

Pentru primul exemplu, avem P = 1, deci pentru cele T = 3 instanţe se cere numai dacă se pot transforma în tablă de şah prin interschimbări de linii şi/sau coloane. Pentru prima instanţă acest lucru nu este posibil, deoarece nu avem niciun 0 ı̂n matrice. Pentru cea de-a doua instanţă, putem efectua următoarele operaţii:


\begin{matrix} 1100 \\ 1100 \\ 0011 \\ 0011 \end{matrix} \xrightarrow{\texttt{L 2 3}}
\begin{matrix} 1100 \\ \textbf{0011} \\ \textbf{1100} \\ 0011 \end{matrix} \xrightarrow{\texttt{C 2 3}}
\begin{matrix} 1\textbf{01}0 \\ 0\textbf{10}1 \\ 1\textbf{01}0 \\ 0\textbf{10}1 \end{matrix}

Pentru ultima instanţă, matricea A este deja tablă de şah. Pentru al doilea exemplu, avem P = 2, deci pentru cele T = 2 instanţe se cere numărul minim de operaţii pentru a le transforma în tablă de şah. Pentru prima instanţă, o solutie cu 2 operaţii este prezentată mai sus, şi nu există soluţii mai scurte. Pentru cea de-a doua instanţă, matricea este deja tablă de şah, deci răspunsul este 0.

Al treilea exemplu este exact ca anteriorul, numai că avem P = 3, deci trebuie tipărite exact care sunt operaţiile ce aduc matricea la forma de tablă de şah. Pentru punctaj maxim pe acest exemplu, ar fi obligatoriu să afişăm o soluţie cu 2 operaţii (adică număr minim), cum ar fi cea de mai sus. Cu toate acestea, cu scop demonstrativ, noi venim cu o soluţie compusă din 3 operaţii, prin care obţinem doar 50% din punctaj:


\begin{matrix} 1100 \ 1100 \ 0011 \ 0011 \end{matrix} \xrightarrow{\texttt{L 2 4}}
\begin{matrix} 1100 \ \textbf{0011} \ 0011 \ \textbf{1100} \end{matrix} \xrightarrow{\texttt{C 2 3}}
\begin{matrix} 1\textbf{01}0 \ 0\textbf{10}1 \ 0\textbf{10}1 \ 1\textbf{01}0 \end{matrix} \xrightarrow{\texttt{L 1 2}}
\begin{matrix} \textbf{0101} \ \textbf{1010} \ 0101 \ 1010 \end{matrix}
‎‎

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?