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

Intrare

determinantain.txt

3

1 1

2 2

3 3

Iesire

Datele introduse corespund restrictiilor impuse.

determinantaout.txt

1

Exemplul 2

Intrare

determinantain.txt

3

2 2

3 3

2 2

Iesire

Datele introduse nu corespund restrictiilor impuse

determinantaout.txt

Rezolvare

def citeste_matrice(file_name):
    with open(file_name, 'r') as file:
        n = int(file.readline())
        matrice = [[0] * n for _ in range(n)]
        for _ in range(n):
            l, c = map(int, file.readline().split())
            matrice[l - 1][c - 1] = 1
        return matrice, n

def calculeaza_determinant(matrice, dimensiune):
    if dimensiune == 1:
        return matrice[0][0]

    determinant = 0
    for i in range(dimensiune):
        sub_matrice = [rand[:i] + rand[i + 1:] for rand in matrice[1:]]
        semn = (-1) ** i
        determinant += semn * matrice[0][i] * calculeaza_determinant(sub_matrice, dimensiune - 1)

    return determinant

def scrie_rezultat(file_name, rezultat):
    with open(file_name, 'w') as file:
        file.write(str(rezultat) + '\n')

if __name__ == "__main__":
    input_file = "determinantain.txt"
    output_file = "determinantaout.txt"

    matrice, dimensiune = citeste_matrice(input_file)
    rezultat_determinant = calculeaza_determinant(matrice, dimensiune)
    scrie_rezultat(output_file, rezultat_determinant)