3508 - Bal: Diferență între versiuni
De la Universitas MediaWiki
Fără descriere a modificării |
|||
(Nu s-a afișat o versiune intermediară efectuată de același utilizator) | |||
Linia 37: | Linia 37: | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python3" line="1"> | <syntaxhighlight lang="python3" line="1"> | ||
MOD = 1000000007 | |||
def numar_moduri_cuplare(n, matrice): | |||
dp = [[0] * (1 << n) for _ in range(n + 1)] | |||
dp[0][0] = 1 | |||
for i in range(1, n + 1): | |||
for mask in range(1 << n): | |||
num_bits = bin(mask).count('1') | |||
for j in range(n): | |||
if matrice[i-1][j] == 1 and (mask & (1 << j)) == 0: | |||
dp[i][mask | (1 << j)] = (dp[i][mask | (1 << j)] + dp[i-1][mask]) % MOD | |||
rezultat = sum(dp[n]) | |||
return rezultat % MOD | |||
def verificare(n, matrice, rezultat): | |||
if not (1 < n < 25): | |||
return False | return False | ||
if rezultat < 0 or rezultat >= MOD: | |||
return False | |||
for | for i in range(n): | ||
for j in range(n): | |||
if matrice[i][j] not in {0, 1}: | |||
return False | |||
return | return True | ||
# Citire | # Citire date de intrare | ||
n = int(input("Introduceți numărul n: ")) | n = int(input("Introduceți numărul n: ")) | ||
matrice_adiacenta = [list(map(int, input().split())) for _ in range(n)] | matrice_adiacenta = [list(map(int, input().split())) for _ in range(n)] | ||
# Calcul și afișare rezultat | # Calcul și afișare rezultat | ||
rezultat = | rezultat = numar_moduri_cuplare(n, matrice_adiacenta) | ||
print(rezultat) | |||
# Verificare și afișare rezultat | |||
if verificare(n, matrice_adiacenta, rezultat): | |||
print(rezultat) | |||
else: | |||
print("Datele introduse nu corespund restrictiilor impuse.") | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Versiunea curentă din 29 decembrie 2023 11:54
Cerinta
La balul din acest an participă n băieți și n fete, numerotați de la 1 la n. Compatibilitățile dintre aceștia pot fi reprezentate sub forma unui graf bipartit. Fie mat matricea de adiacentă. Atunci, băiatul i se poate cupla cu fata j doar dacă sunt compatibili, adică mat[i][j] = 1. Aflați numărul de moduri de a forma cele n cupluri.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi matricea de adiacență.
Date de iesire
Programul va afișa pe ecran numărul de moduri de a forma cuplurile, modulo 1.000.000.007.
Restrictii si precizari
- 1 < n < 25
Exemplul 1
- Intrare
- 3
- 0 1 1
- 1 0 1
- 1 1 1
- Iesire
- Datele introduse corespund restrictiilor impuse
- 3
Exemplul 2
- Intrare
- 3
- -5 34 0
- 3 87 0
- 0 0 -1
- Iesire
- Datele introduse nu corespund restrictiilor impuse
Rezolvare
MOD = 1000000007
def numar_moduri_cuplare(n, matrice):
dp = [[0] * (1 << n) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
for mask in range(1 << n):
num_bits = bin(mask).count('1')
for j in range(n):
if matrice[i-1][j] == 1 and (mask & (1 << j)) == 0:
dp[i][mask | (1 << j)] = (dp[i][mask | (1 << j)] + dp[i-1][mask]) % MOD
rezultat = sum(dp[n])
return rezultat % MOD
def verificare(n, matrice, rezultat):
if not (1 < n < 25):
return False
if rezultat < 0 or rezultat >= MOD:
return False
for i in range(n):
for j in range(n):
if matrice[i][j] not in {0, 1}:
return False
return True
# Citire date de intrare
n = int(input("Introduceți numărul n: "))
matrice_adiacenta = [list(map(int, input().split())) for _ in range(n)]
# Calcul și afișare rezultat
rezultat = numar_moduri_cuplare(n, matrice_adiacenta)
# Verificare și afișare rezultat
if verificare(n, matrice_adiacenta, rezultat):
print(rezultat)
else:
print("Datele introduse nu corespund restrictiilor impuse.")
Explicatie
Cele 3 modalități sunt:
- (1, 2), (2, 1), (3, 3)
- (1, 2), (2, 3), (3, 1)
- (1, 3), (2, 1), (3, 2)