3508 - Bal: Difference between revisions

Latest revision as of 11:54, 29 December 2023

Cerinta[edit | edit source]

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[edit | edit source]

Programul citește de la tastatură numărul n, iar apoi matricea de adiacență.

Date de iesire[edit | edit source]

Programul va afișa pe ecran numărul de moduri de a forma cuplurile, modulo 1.000.000.007.

Restrictii si precizari[edit | edit source]

1 < n < 25

Exemplul 1[edit | edit source]

Intrare: 3; 0 1 1; 1 0 1; 1 1 1
Iesire: Datele introduse corespund restrictiilor impuse; 3

Exemplul 2[edit | edit source]

Intrare: 3; -5 34 0; 3 87 0; 0 0 -1
Iesire: Datele introduse nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<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

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

</syntaxhighlight>

Explicatie[edit | edit source]

Cele 3 modalități sunt:

(1, 2), (2, 1), (3, 3)

(1, 2), (2, 3), (3, 1)

(1, 3), (2, 1), (3, 2)

@@ Line 1: / Line 1: @@
 == 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.
+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ță.
+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.
+Programul va afișa pe ecran numărul de moduri de a forma cuplurile, modulo '''1.000.000.007'''.
 == Restrictii si precizari ==
@@ Line 22: / Line 22: @@
 :1 1 1
 ;Iesire
-;Datele introduse corespund restrictiilor impuse
+:Datele introduse corespund restrictiilor impuse
 :3
@@ Line 32: / Line 32: @@
 :0 0 -1
 ;Iesire
-;Datele introduse nu corespund restrictiilor impuse
+:Datele introduse nu corespund restrictiilor impuse
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-def numara_cupluri(mat, n):
+MOD = 1000000007
-    MOD = 1000000007
-    def dfs(baiat, vazut):
+def numar_moduri_cuplare(n, matrice):
-        vazut[baiat] = True
+    dp = [[0] * (1 << n) for _ in range(n + 1)]
-        for fata in range(n):
+    dp[0][0] = 1
-            if mat[baiat][fata] and not vazut[n + fata]:
-                vazut[n + fata] = True
-                if perechi[n + fata] == -1 or dfs(perechi[n + fata], vazut):
+    for i in range(1, n + 1):
-                    perechi[n + fata] = baiat
+        for mask in range(1 << n):
-                    return True
+            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
-     perechi = [-1] * (2 * n)
+     if rezultat < 0 or rezultat >= MOD:
-    rezultat = 0
+        return False
-     for baiat in range(n):
+     for i in range(n):
-         vazut = [False] * (2 * n)
+         for j in range(n):
-        if dfs(baiat, vazut):
+            if matrice[i][j] not in {0, 1}:
-            rezultat += 1
+                return False
-     return rezultat % MOD
+     return True
-# Citire număr de băieți/fete și matricea de adiacență
+# 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 = numara_cupluri(matrice_adiacenta, n)
+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>