3508 - Bal: Difference between revisions

Revision as of 10:10, 27 December 2023

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

<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

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) print(rezultat)

</syntaxhighlight>

Explicatie

Cele 3 modalități sunt:

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

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

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

@@ Line 37: / Line 37: @@
 == 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')
-        return False
+            for j in range(n):
+                if matrice[i-1][j] == 1 and (mask & (1 << j)) == 0:
-    perechi = [-1] * (2 * n)
+                    dp[i][mask | (1 << j)] = (dp[i][mask | (1 << j)] + dp[i-1][mask]) % MOD
-    rezultat = 0
-    for baiat in range(n):
-        vazut = [False] * (2 * n)
-        if dfs(baiat, vazut):
-            rezultat += 1
+    rezultat = sum(dp[n])
      return rezultat % MOD
-# 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)
 </syntaxhighlight>