1693 - Transform

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.

Cerința

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 de intrare transformin.txt 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 de ieșire transformout.txt 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 și precizări

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

Exemplul 1

transformin.txt

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

transformout.txt

L 3 4

C 3 2

0 0 0

Exemplul 2

transformin.txt

3

1 1

2 2

3 3

2 1

1 3

2 2

1 1

2 2

3 3

3 1

1 3

2 1

3 1

1 1

2 2

0 0

transformout.txt

L 2 3

L 1 2

C 1 2

0 0 0

Rezolvare

<syntaxhighlight lang="python" line>

1. 1693 - Transform

def interschimbare_linie(matrice, linie1, linie2):

   for coloana in range(len(matrice[0])):
       matrice[linie1][coloana], matrice[linie2][coloana] = matrice[linie2][coloana], matrice[linie1][coloana]

def interschimbare_coloana(matrice, coloana1, coloana2):

   for linie in range(len(matrice)):
       matrice[linie][coloana1], matrice[linie][coloana2] = matrice[linie][coloana2], matrice[linie][coloana1]

def afisare_transformare(operatii):

   with open("transformout.txt", "w") as output_file:
       for op in operatii:
           output_file.write(f"{op[0]} {op[1]} {op[2]}\n")
       output_file.write("0 0 0\n")

def main():

   with open("transformin.txt", "r") as input_file:
       N = int(input_file.readline())
       if not (1 <= N <= 80000):
           print("Fals")
           return

       matrice_A = [[0] * N for _ in range(N)]
       matrice_B = [[0] * N for _ in range(N)]

       for _ in range(2 * N):
           linie, coloana = map(int, input_file.readline().split())
           if not (1 <= linie <= N and 1 <= coloana <= N):
               print("Fals")
               return
           matrice_A[linie - 1][coloana - 1] = 1

       for _ in range(2 * N):
           linie, coloana = map(int, input_file.readline().split())
           if not (1 <= linie <= N and 1 <= coloana <= N):
               print("Fals")
               return
           matrice_B[linie - 1][coloana - 1] = 1

   operatii = []

   for i in range(N):
       for j in range(N):
           if matrice_A[i][j] == 1:
               operatii.append(('L', i + 1, j + 1))
               interschimbare_linie(matrice_B, i, j)
               break

       for j in range(N):
           if matrice_A[j][i] == 1:
               operatii.append(('C', i + 1, j + 1))
               interschimbare_coloana(matrice_B, i, j)
               break

   afisare_transformare(operatii)

if __name__ == "__main__":

   main()

</syntaxhighlight>