polihroniade

Polihroniade

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

!>problema/polihroniade?polih2.jpeg!
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 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:

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:

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

# 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$ .
# 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 renumiti, să il ajutati in a transforma matricea $A$ intr-o tablă de sah. Pentru aceasta, Victor are nevoie de următoarele informatii:

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:

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

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

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.

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

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.

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

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

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

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

Î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ă:

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

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

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

h2. Pentru 40 de puncte

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

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

h2. Exemple

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

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:

<tex>
\begin{matrix} 1100 \\ 1100 \\ 0011 \\ 0011 \end{matrix} \xrightarrow{\texttt{L 2 3}}

\begin{matrix} 1\textbf{01}0 \\ 0\textbf{10}1 \\ 1\textbf{01}0 \\ 0\textbf{10}1 \end{matrix}
</tex>

Pentru ultima instantă, matricea $A$ este deja tablă de sah. Pentru al doilea exemplu, avem $P = 2$, deci pentru cele $T = 2$ instante se cere numărul minim de operatii pentru a le transforma in tablă de sah. Pentru prima instantă, o solutie cu $2$ operatii este prezentată mai sus, si nu există solutii mai scurte. Pentru cea de-a doua instantă, matricea este deja tablă de sah, deci răspunsul este $0$.

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 operatiile ce aduc matricea la forma de tablă de sah. Pentru punctaj maxim pe acest exemplu, ar fi obligatoriu să afisăm o solutie cu 2 operatii (adică număr minim), cum ar fi cea de mai sus. Cu toate acestea, cu scop demonstrativ, noi venim cu o solutie compusă din 3 operatii, +*prin care obtinem doar $50%$ din punctaj:*+

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:*+

<tex>
\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}

</tex>

‎‎

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