| Fişierul intrare/ieşire: | transform2.in, transform2.out | Sursă | ONI 2016, clasele 11-12 |
| Autor | Zoltan Szabo | Adăugată de |  Andrei Constantinescu •Andrei1998 |
| Timp execuţie pe test | 1.75 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
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.
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.
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.
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.
Exemplu
| 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 |
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.
