Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2021-03-23 09:50:22.
Revizia anterioară   Revizia următoare  

 

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

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


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

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:


\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?