4194 - EchipaFB: Difference between revisions

Revision as of 09:15, 27 December 2023

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"> MODULO = 998244353

def calculeaza_moduri(F, B):

   rezultate = []
   total_elevi = F + B

   for K in range(1, total_elevi + 1):
       moduri = 0
       for numar_fete in range(1, min(K, F) + 1, 2):
           numar_baieti = K - numar_fete
           if numar_baieti <= B:
               moduri += 1

       rezultate.append(moduri % MODULO)

   return rezultate

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>

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.

@@ Line 31: / Line 31: @@
 <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>