3935 - determinanta

From Bitnami 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

Intrare
determinantain.txt
3
1 1
2 2
3 3
Iesire
Datele introduse corespund restrictiilor impuse.
determinantaout.txt
1

Exemplul 2

Intrare
determinanta.txt
3
2 2
3 3
2 2
Iesire
Datele introduse nu corespund restrictiilor impuse
determinanta.txt


Rezolvare

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

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.txt')
   # Calculeaza determinantul
   determinant = calculeaza_determinant(matrice)
   # Scrie determinantul in fisier
   scrie_determinant_in_fisier('determinanta.txt', 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.txt')
   # Calculeaza determinantul
   determinant = calculeaza_determinant(matrice)
   # Scrie determinantul in fisier
   scrie_determinant_in_fisier('determinanta.txt', determinant)

if __name__ == "__main__":

   main()

</syntaxhighlight>