Fişierul intrare/ieşire:transform2.in, transform2.outSursăONI 2016, clasele 11-12
AutorZoltan SzaboAdăugată deAndrei1998Constantinescu Andrei-Costin Andrei1998
Timp execuţie pe test3.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.intransform2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?