3935 - determinanta
De la Universitas MediaWiki
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
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)