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

!>problema/polihroniade?polih2.jpeg!

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

\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") ==