4194 - EchipaFB - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T11:24:26Z

Rezolvare

← Older revision		Revision as of 11:24, 29 December 2023
Line 32:		Line 32:
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	MODULO = 998244353		MODULO = 998244353

			def este_input_valid(F, B):
			return 1 <= F <= 100000 and 1 <= B <= 100000

	def calculeaza_moduri(F, B):		def calculeaza_moduri(F, B):
Line 48:		Line 51:
	return rezultate		return rezultate

	# Citire date de intrare		if __name__ == "__main__":
	F = int(input("~~Introduceti numarul~~ de fete (F): "))		# Citire date de intrare
	B = int(input("~~Introduceti numarul~~ de ~~baieti~~ (B): "))		F = int(input("Introduceți numărul de fete (F): "))
			B = int(input("Introduceți numărul de băieți (B): "))

			# Verificare validitate date de intrare
			if not este_input_valid(F, B):
			print("Datele introduse nu corespund restricțiilor impuse.")
			else:
			# Calcul și afișare rezultate
			rezultate = calculeaza_moduri(F, B)
			for K, moduri in enumerate(rezultate, start=1):
			print(f"Pentru K = {K}, numărul de moduri este: {moduri}")

	~~# Calcul si afisare rezultate~~
	~~rezultate = calculeaza_moduri(F, B)~~
	~~for K, moduri in enumerate(rezultate, start=1):~~
	~~print(f"Pentru K = {K}, numarul de moduri este: {moduri}")~~

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa: /* Rezolvare */

2023-12-27T09:15:35Z

Rezolvare

← Older revision		Revision as of 09:15, 27 December 2023
Line 31:		Line 31:

	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	~~MOD~~ = 998244353		MODULO = 998244353

	def ~~comb~~(n, k):		def calculeaza_moduri(F, B):
	~~# Calculează coeficientul binomial C(n, k) % MOD folosind metoda combinatorică modulară~~		rezultate = []
	~~result~~ = 1		total_elevi = F + B
	~~for i in range(1, k + 1):~~
	~~result~~ = ~~(result * (n - i~~ + ~~1) * pow(i, -1, MOD)) % MOD~~
	~~return result~~

	~~def count_ways(F, B):~~		for K in range(1, total_elevi + 1):
	~~# Calculăm numărul de moduri pentru fiecare K de la 1 la F+B~~		moduri = 0
	for K in range(1, ~~F + B~~ + 1):		for numar_fete in range(1, min(K, F) + 1, 2):
	~~# Numărul de~~ moduri ~~în care putem forma o echipă cu un număr impar de fete~~		numar_baieti = K - numar_fete
	~~# este dat de suma combinărilor C(F, i) * C(B, K - i) pentru i de la 1 la min(K, F)~~		if numar_baieti <= B:
	~~ways~~ = 0		moduri += 1
	for i in range(1, min(K, F) + 1, 2):
	~~ways~~ = ~~(ways + comb(F, i) * comb(B,~~ K - ~~i)) % MOD~~

	~~print(ways)~~

	~~if __name__ == "__main__":~~		rezultate.append(moduri % MODULO)
	~~# Citim numerele F și B de la tastatură~~
	~~F = int~~(~~input("Introduceți numărul de fete (F): "))~~
	~~B = int(input("Introduceți numărul de băieți (B): ")~~)

	# ~~Calculăm și afișăm rezultatele~~		return rezultate
	~~count_ways~~(F, B)
			# Citire date de intrare
			F = int(input("Introduceti numarul de fete (F): "))
			B = int(input("Introduceti numarul de baieti (B): "))

			# Calcul si afisare rezultate
			rezultate = calculeaza_moduri(F, B)
			for K, moduri in enumerate(rezultate, start=1):
			print(f"Pentru K = {K}, numarul de moduri este: {moduri}")

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa: /* Exemplul 2 */

2023-12-27T08:28:15Z

Exemplul 2

← Older revision		Revision as of 08:28, 27 December 2023
Line 26:		Line 26:
	:-10 7		:-10 7
	;Iesire		;Iesire
	;Datele introduse nu corespund restrictiilor impuse		:Datele introduse nu corespund restrictiilor impuse


	== Rezolvare ==		== Rezolvare ==

Mesarosdenisa at 08:27, 27 December 2023

2023-12-27T08:27:52Z

← Older revision		Revision as of 08:27, 27 December 2023
Line 1:		Line 1:
	== Cerinta ==		== Cerinta ==

	Într-o şcoală sunt F fete şi B băieţi. Pentru fiecare valoare a lui K de la 1 la F+B, aflaţi în câte moduri se poate alcătui o echipă formată din K elevi, care să conţină un număr impar de fete.		Într-o şcoală sunt '''F''' fete şi '''B''' băieţi. Pentru fiecare valoare a lui '''K''' de la '''1''' la '''F+B''', aflaţi în câte moduri se poate alcătui o echipă formată din '''K''' elevi, care să conţină un număr impar de fete.

	== Date de intrare ==		== Date de intrare ==

	Programul citește de la tastatură numerele F şi B.		Programul citește de la tastatură numerele '''F''' şi '''B'''.

	== Date de iesire ==		== Date de iesire ==

	Programul va afișa pe ecran, pentru fiecare K de la 1 la F+B, numărul de moduri în care putem forma echipa, modulo 998244353.		Programul va afișa pe ecran, pentru fiecare '''K''' de la '''1''' la '''F+B''', numărul de moduri în care putem forma echipa, modulo '''998244353'''.

	== Restrictii si precizari ==		== Restrictii si precizari ==

	*1 ≤ F,B ≤ 100.000		*1 &les; F,B &les; 100.000

	== Exemplul 1 ==		== Exemplul 1 ==
Line 32:		Line 32:

	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	def ~~combinatoriala_modulara~~(n, k, ~~mod~~):		MOD = 998244353

			def comb(n, k):
			# Calculează coeficientul binomial C(n, k) % MOD folosind metoda combinatorică modulară
	result = 1		result = 1
	for i in range(k):		for i in range(1, k + 1):
	result = (result * (n - i)~~) % mod~~		result = (result * (n - i + 1) * pow(i, -1, MOD)) % MOD
	~~result = (result~~ * pow(i ~~+ 1~~, ~~mod~~ - 2, ~~mod~~)) % ~~mod~~
	return result		return result

	def ~~numar_moduri_echipe~~(F, B):		def count_ways(F, B):
	~~mod = 998244353~~		# Calculăm numărul de moduri pentru fiecare K de la 1 la F+B
	~~result = []~~

	for K in range(1, F + B + 1):		for K in range(1, F + B + 1):
	~~numar_fete_impar~~ = min(F, K)		# Numărul de moduri în care putem forma o echipă cu un număr impar de fete
	~~numar_fete_par~~ = K - ~~numar_fete_impar~~		# este dat de suma combinărilor C(F, i) * C(B, K - i) pentru i de la 1 la min(K, F)
			ways = 0
			for i in range(1, min(K, F) + 1, 2):
			ways = (ways + comb(F, i) * comb(B, K - i)) % MOD

			print(ways)

	if ~~numar_fete_impar % 2~~ == 1:		if __name__ == "__main__":
	~~numar_moduri~~ = (~~combinatoriala_modulara~~(F~~, numar_fete_impar, mod~~) *		# Citim numerele F și B de la tastatură
	~~combinatoriala_modulara(B, numar_fete_par, mod~~)) ~~% mod~~		F = int(input("Introduceți numărul de fete (F): "))
	~~result.append~~(~~numar_moduri~~)		B = int(input("Introduceți numărul de băieți (B): "))
	~~else~~:
	~~result.append(0~~)

	~~return result~~		# Calculăm și afișăm rezultatele
			count_ways(F, B)

	~~def main():~~
	~~# Citirea datelor de intrare de la tastatură~~
	~~F = int(input("Numărul de fete (F): "))~~
	~~B = int(input("Numărul de băieți (B): "))~~

	~~# Calcularea și afișarea rezultatelor~~
	~~rezultate = numar_moduri_echipe(F, B)~~
	~~for K, numar_moduri in enumerate(rezultate, start=1):~~
	~~print(f"Pentru K = {K}, numărul de moduri este {numar_moduri}")~~

	~~if __name__ == "__main__":~~
	~~main()~~
	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa at 10:08, 12 December 2023

2023-12-12T10:08:52Z

← Older revision		Revision as of 10:08, 12 December 2023
Line 17:		Line 17:
	== Exemplul 1 ==		== Exemplul 1 ==
	;Intrare		;Intrare
	;3 2		:3 2
	;Iesire		;Iesire
	;Datele introduse corespund restrictiilor impuse		;Datele introduse corespund restrictiilor impuse
	;3 6 4 2 1		:3 6 4 2 1

	== Exemplul 2 ==		== Exemplul 2 ==
	;Intrare		;Intrare
	;-10 7		:-10 7
	;Iesire		;Iesire
	;Datele introduse nu corespund restrictiilor impuse		;Datele introduse nu corespund restrictiilor impuse

Mesarosdenisa: Pagină nouă: == Cerinta == Într-o şcoală sunt F fete şi B băieţi. Pentru fiecare valoare a lui K de la 1 la F+B, aflaţi în câte moduri se poate alcătui o echipă formată din K elevi, care să conţină un număr impar de fete. == Date de intrare == Programul citește de la tastatură numerele F şi B. == Date de iesire == Programul va afișa pe ecran, pentru fiecare K de la 1 la F+B, numărul de moduri în care putem forma echipa, modulo 998244353. == Restrictii si preciz...

2023-12-12T09:09:42Z

Pagină nouă: == Cerinta == Într-o şcoală sunt F fete şi B băieţi. Pentru fiecare valoare a lui K de la 1 la F+B, aflaţi în câte moduri se poate alcătui o echipă formată din K elevi, care să conţină un număr impar de fete. == Date de intrare == Programul citește de la tastatură numerele F şi B. == Date de iesire == Programul va afișa pe ecran, pentru fiecare K de la 1 la F+B, numărul de moduri în care putem forma echipa, modulo 998244353. == Restrictii si preciz...

New page

== Cerinta ==

Într-o şcoală sunt F fete şi B băieţi. Pentru fiecare valoare a lui K de la 1 la F+B, aflaţi în câte moduri se poate alcătui o echipă formată din K elevi, care să conţină un număr impar de fete.

== Date de intrare ==

Programul citește de la tastatură numerele F şi B.

== Date de iesire ==

Programul va afișa pe ecran, pentru fiecare K de la 1 la F+B, numărul de moduri în care putem forma echipa, modulo 998244353.

== Restrictii si precizari ==

*1 ≤ F,B ≤ 100.000

== Exemplul 1 ==
;Intrare
;3 2
;Iesire
;Datele introduse corespund restrictiilor impuse
;3 6 4 2 1

== Exemplul 2 ==
;Intrare
;-10 7
;Iesire
;Datele introduse nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def combinatoriala_modulara(n, k, mod):
result = 1
for i in range(k):
result = (result * (n - i)) % mod
result = (result * pow(i + 1, mod - 2, mod)) % mod
return result

def numar_moduri_echipe(F, B):
mod = 998244353
result = []

for K in range(1, F + B + 1):
numar_fete_impar = min(F, K)
numar_fete_par = K - numar_fete_impar

if numar_fete_impar % 2 == 1:
numar_moduri = (combinatoriala_modulara(F, numar_fete_impar, mod) *
combinatoriala_modulara(B, numar_fete_par, mod)) % mod
result.append(numar_moduri)
else:
result.append(0)

return result

def main():
# Citirea datelor de intrare de la tastatură
F = int(input("Numărul de fete (F): "))
B = int(input("Numărul de băieți (B): "))

# Calcularea și afișarea rezultatelor
rezultate = numar_moduri_echipe(F, B)
for K, numar_moduri in enumerate(rezultate, start=1):
print(f"Pentru K = {K}, numărul de moduri este {numar_moduri}")

if __name__ == "__main__":
main()
</syntaxhighlight>

== Explicatie ==

Să notăm cu A,B,C fetele şi cu X,Y băieţii. Pentru K=1 echipele pot fi A, B, respectiv C. Pentru K=2: AX, AY, BX, BY, CX, CY. Pentru K=3: AXY, BXY, CXY, ABC. Pentru K=4: ABCX, ABCY. Pentru K=5: ABCXY.