4194 - EchipaFB: Difference between revisions

Revision as of 08:27, 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"> MOD = 998244353

def comb(n, k):

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

def count_ways(F, B):

   # Calculăm numărul de moduri pentru fiecare K de la 1 la F+B
   for K in range(1, F + B + 1):
       # Numărul de moduri în care putem forma o echipă cu un număr impar de fete
       # 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 __name__ == "__main__":

   # 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
   count_ways(F, B)

</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 1: / Line 1: @@
 == 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 ==
-Programul citește de la tastatură numerele F şi B.
+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.
+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
+*1 &les; F,B &les; 100.000
 == Exemplul 1 ==
@@ Line 32: / Line 32: @@
 <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
-     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
-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):
-         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>