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 este_intrare_valida(n, pozitii):
# Verificăm dacă toate pozițiile sunt în limitele matricei
for linie, coloana in pozitii:
if not (1 <= linie <= n and 1 <= coloana <= n):
return False
return True
def citeste_intrare(numefisier):
with open(numefisier, 'r') as fisier:
n = int(fisier.readline())
pozitii = [tuple(map(int, fisier.readline().split())) for _ in range(n)]
if este_intrare_valida(n, pozitii):
matrice = [[0] * n for _ in range(n)]
for linie, coloana in pozitii:
matrice[linie - 1][coloana - 1] = 1
return matrice, n
else:
raise ValueError("Date de intrare nevalide")
def scrie_iesire(numefisier, rezultat):
with open(numefisier, 'w') as fisier:
fisier.write(str(rezultat) + '\n')
def calculeaza_determinant(matrice, dimensiune):
# Cazul de bază: matrice de dimensiune 2x2
if dimensiune == 2:
return matrice[0][0] * matrice[1][1] - matrice[0][1] * matrice[1][0]
determinant = 0
for i in range(dimensiune):
# Eliminăm linia și coloana corespunzătoare elementului selectat
submatrice = [linie[:i] + linie[i+1:] for linie in matrice[1:]]
semn = (-1) ** i
determinant += semn * matrice[0][i] * calculeaza_determinant(submatrice, dimensiune - 1)
return determinant
if __name__ == "__main__":
fisier_intrare = "determinantain.txt"
fisier_iesire = "determinantaout.txt"
try:
# Citim matricea și dimensiunea din fișierul de intrare
matrice, dimensiune = citeste_intrare(fisier_intrare)
# Calculăm determinantul
rezultat_determinant = calculeaza_determinant(matrice, dimensiune)
# Scriem rezultatul în fișierul de ieșire
scrie_iesire(fisier_iesire, rezultat_determinant)
except ValueError as e:
print(f"Eroare: {e}")