3935 - determinanta

Cerinta

Se consideră o matrice cu n linii şi n coloane şi elemente egale cu 0 sau 1. Să se calculeze determinantul matricei.

Date de intrare

Fișierul de intrare determinantain.txt conține pe prima linie numărul n, iar pe următoarele n linii câte o pereche de numere naturale l, c, reprezentând faptul că elementul matricei de pe linia l şi coloana c are valoarea 1.

Date de iesire

Fișierul de ieșire determinantaout.txt va conține pe prima linie valoarea determinantului matricei.

Restrictii si precizari

• 2 ⩽ n ⩽ 100.000
• 1 ⩽ l,c ⩽ n
• Exceptând elementele din poziţiile (l,c), care sunt egale cu 1, celelalte elemente ale matricei au valoarea 0.

Exemplul 1

determinantain.txt

3

1 1

2 2

3 3

Datele introduse corespund restrictiilor impuse.

determinantaout.txt

1

Exemplul 2

determinantain.txt

3

2 2

3 3

2 2

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1">

def calc_determinant(matrix, size):

   # Cazul de bază: matrice de dimensiune 2x2
   if size == 2:
       return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]

   determinant = 0
   for i in range(size):
       # Eliminăm linia și coloana corespunzătoare elementului selectat
       sub_matrix = [row[:i] + row[i+1:] for row in matrix[1:]]
       sign = (-1) ** i
       determinant += sign * matrix[0][i] * calc_determinant(sub_matrix, size - 1)

   return determinant

def read_input(file_name):

   with open(file_name, 'r') as file:
       n = int(file.readline())
       matrix = [[0] * n for _ in range(n)]
       for _ in range(n):
           l, c = map(int, file.readline().split())
           matrix[l-1][c-1] = 1
       return matrix, n

def write_output(file_name, result):

   with open(file_name, 'w') as file:
       file.write(str(result) + '\n')

if __name__ == "__main__":

   input_file = "determinantain.txt"
   output_file = "determinantaout.txt"

   # Citim matricea și dimensiunea din fișierul de intrare
   matrix, size = read_input(input_file)
   
   # Calculăm determinantul
   determinant_result = calc_determinant(matrix, size)
   
   # Scriem rezultatul în fișierul de ieșire
   write_output(output_file, determinant_result)

</syntaxhighlight>