3508 - Bal - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T11:54:01Z

Rezolvare

@@ Line 53: / Line 53: @@
      rezultat = sum(dp[n])
      return rezultat % MOD
 # Citire date de intrare
@@ Line 60: / Line 74: @@
 # Calcul și afișare rezultat
 rezultat = numar_moduri_cuplare(n, matrice_adiacenta)
 print(rezultat)

Mesarosdenisa: /* Rezolvare */

2023-12-27T10:10:21Z

Rezolvare

← Older revision		Revision as of 10:10, 27 December 2023
Line 37:		Line 37:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<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		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: "))		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 = ~~numara_cupluri~~(matrice_adiacenta~~, n~~)		rezultat = numar_moduri_cuplare(n, matrice_adiacenta)
	print(rezultat)		print(rezultat)


	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa at 10:08, 27 December 2023

2023-12-27T10:08:58Z

← Older revision		Revision as of 10:08, 27 December 2023
Line 1:		Line 1:
	== Cerinta ==		== 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 ==		== 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 ==		== 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 ==		== Restrictii si precizari ==
Line 22:		Line 22:
	:1 1 1		:1 1 1
	;Iesire		;Iesire
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:3		:3

Line 32:		Line 32:
	:0 0 -1		:0 0 -1
	;Iesire		;Iesire
	;Datele introduse nu corespund restrictiilor impuse		:Datele introduse nu corespund restrictiilor impuse

Mesarosdenisa: Pagină nouă: == 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 d...

2023-12-12T12:34:47Z

Pagină nouă: == 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 d...

New page

== 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">
def numara_cupluri(mat, n):
MOD = 1000000007

def dfs(baiat, vazut):
vazut[baiat] = True
for fata in range(n):
if mat[baiat][fata] and not vazut[n + fata]:
vazut[n + fata] = True

if perechi[n + fata] == -1 or dfs(perechi[n + fata], vazut):
perechi[n + fata] = baiat
return True

return False

perechi = [-1] * (2 * n)
rezultat = 0

for baiat in range(n):
vazut = [False] * (2 * n)
if dfs(baiat, vazut):
rezultat += 1

return rezultat % MOD

# Citire număr de băieți/fete și matricea de adiacență
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)
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)