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 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}")

</syntaxhighlight>