== include(page="template/taskheader" task_id="transform2") ==
O matrice pătratică de dimensiuni $N x N$ cu liniile şi coloanele indexate de la $1$ la $N$ se numeşte *matrice şmecheră de Calafat* dacă pe fiecare linie şi fiecare coloană există exact două valori de $1$, restul elementelor fiind $0$.
h2. Cerinta
Având două *matrice şmechere de Calafat* notate cu $A$ şi $B$, se cere ca prin interschimbări de linii şi coloane să se transforme matricea $B$ în matricea $A$.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul $transform2.in$ conţine pe prima linie numărul $N$, reprezentând dimensiunea matricei. Pe următoarele $2N$ linii avem câte o pereche de numere naturale separate prin spaţiu, reprezentând linia şi coloana unui element de valoare $1$ din matricea $A$. În continuare pe următoarele $2N$ linii avem câte o pereche de numere naturale separate prin spaţiu, reprezentând linia şi coloana unui element de valoare $1$ din matricea $B$.
Fişierul de intrare $transform2.in$ ...
h2. Date de ieşire
Fişierul $transform2.out$ va conţine pe fiecare linie câte o operaţie de interschimbare a două linii sau două coloane, codificată printr-un triplet $ch x y$ format dintr-un caracter $ch$ şi două numere naturale $x$ şi $y$ separate prin câte un spaţiu. Valoarea lui $ch$ de fiecare dată poate fi doar $'L'$ , $'C'$ sau $'0'$. Dacă valoarea lui $ch$ este egală cu $'L'$, atunci se vor interschimba liniile $x$ şi $y$ în matricea $B$. Dacă valoarea lui $ch$ este egală cu $'C'$, atunci se vor interschimba coloanele $x$ şi $y$ în matricea $B$. Ultimul triplet de valori introdus în fişierul de ieşire va fi $'0 0 0'$ reprezentând terminarea acţiunii.
În fişierul de ieşire $transform2.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 80000$
* Pentru un program care se încadrează în timpul de execuţie, punctajul acordat depinde de numărul de operaţii tipărite în fişierul de ieşire. Să notăm cu $op$ numărul de operaţii efectuate. Astfel pentru fiecare fişier de ieşire $corect$, punctajul se va acorda astfel:
** dacă $1 ≤ op ≤ 2N$, se acordă $100%$ din punctaj;
** dacă $2N+1 ≤ op ≤ 4N$, se acordă $75%$ din punctaj;
** dacă $op > 4N$, se acordă $50%$ din punctaj.
* Pentru toate testele de intrare există soluţie.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. transform2.in |_. transform2.out |
| 4
1 1
2 2
3 3
4 1
3 4
4 4
2 3
1 2
1 3
2 3
1 1
2 2
4 2
4 4
3 4
3 1
| L 3 4
C 3 2
0 0 0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Prima dată se citeşte matricea $A$:
$1 1 0 0$
$0 1 1 0$
$0 0 1 1$
$1 0 0 1$
Apoi se citeşte matricea $B$:
$1 0 1 0$
$0 1 1 0$
$1 0 0 1$
$0 1 0 1$
Aplicăm operaţia $L 3 4$ interschimbând liniile $3$ şi $4$ în matricea $B$:
$1 0 1 0$
$0 1 1 0$
*$0 1 0 1$*
*$1 0 0 1$*
Aplicăm operaţia $C 3 2$ interschimbând coloanele $3$ şi $2$ în matricea $B$:
$1 *1 0* 0$
$0 *1 1* 0$
$0 *0 1* 1$
$1 *0 0* 1$
Citind linia $0 0 0$ înţelegem că s-au terminat operaţiile şi s-a obţinut matricea $A$.
...
== include(page="template/taskfooter" task_id="transform2") ==
