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

Intrare

3

1 1

2 2

3 3

Iesire

Datele introduse corespund restrictiilor impuse.

1

Exemplul 2

Intrare

3

2 2

3 3

2 2

Iesire

Datele introduse nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1"> import numpy as np

def citeste_matrice_din_fisier(file_path):

   with open(file_path, 'r') as file:
       n = int(file.readline())
       matrice = np.zeros((n, n), dtype=int)
       for _ in range(n):
           l, c = map(int, file.readline().split())
           matrice[l-1][c-1] = 1
   return matrice

def calculeaza_determinant(matrice):

   return int(round(np.linalg.det(matrice)))

def scrie_determinant_in_fisier(file_path, determinant):

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

def main():

   # Citeste matricea din fisier
   matrice = citeste_matrice_din_fisier('determinanta.in')

   # Calculeaza determinantul
   determinant = calculeaza_determinant(matrice)

   # Scrie determinantul in fisier
   scrie_determinant_in_fisier('determinanta.out', determinant)

if __name__ == "__main__":

   main()

import numpy as np

def citeste_matrice_din_fisier(file_path):

   with open(file_path, 'r') as file:
       n = int(file.readline())
       matrice = np.zeros((n, n), dtype=int)
       for _ in range(n):
           l, c = map(int, file.readline().split())
           matrice[l-1][c-1] = 1
   return matrice

def calculeaza_determinant(matrice):

   return int(round(np.linalg.det(matrice)))

def scrie_determinant_in_fisier(file_path, determinant):

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

def main():

   # Citeste matricea din fisier
   matrice = citeste_matrice_din_fisier('determinanta.in')

   # Calculeaza determinantul
   determinant = calculeaza_determinant(matrice)

   # Scrie determinantul in fisier
   scrie_determinant_in_fisier('determinanta.out', determinant)

if __name__ == "__main__":

   main()

</syntaxhighlight>