4194 - EchipaFB: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
Linia 1: Linia 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 ⩽ F,B ⩽ 100.000


== Exemplul 1 ==
== Exemplul 1 ==
Linia 32: Linia 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>


Versiunea de la data 27 decembrie 2023 08:27

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

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)

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.

Adus de la „http://wiki.universitas.ro/index.php?title=4194_-_EchipaFB&oldid=8445”