Editing 3624 - Bal 1

Tocmai a ajuns la balul din sat un grup de '''n''' fete numerotate de la '''1''' la '''n'''. Acolo sunt așteptate de '''m''' băieți frumoși, numerotați de la '''1''' la '''m'''. Fiecare băiat '''i''' ('''i=1..m''') are un coeficient de frumusețe '''b[i]'''. Fetele nu acceptă orice băiat la dans. Fata '''i''' va accepta să danseze cu un băiat doar dacă băiatul are un coeficient de frumusețe mai mare sau egal cu '''f[i]'''.
== Cerinţa ==
Cunoscând coeficienții de frumusețe ai băieților, '''b[1]''', '''b[2]''', …, '''b[m]''' precum și coeficienții preferințelor fetelor, '''f[1]''', '''f[2]''', …, '''f[n]''', să se determine numărul maxim de perechi de dansatori care se poate forma.
== Date de intrare ==
Fișierul de intrare '''balin.txt''' conține pe prima linie numerele '''n''' și '''m'''. Pe a doua linie sunt n numere naturale separate prin spații '''f[1]''', '''f[2]''', …, '''f[n]''' reprezentând coeficienții fetelor, iar pe a treia linie sunt numerele '''b[1]''', '''b[2]''', …, '''b[m]''' reprezentând coeficienții băieților.
== Date de ieșire ==
Fișierul de ieșire '''balout.txt''' va conține un singur număr natural '''P''', reprezentând numărul perechilor '''(f[i], b[j])''' care se poate forma astfel încât '''f[i] &les; b[j]'''.
== Restricţii şi precizări ==
* '''1 &les; n, m &les; 100.000'''
* coeficienții băieților și fetelor sunt numere naturale nenule mai mici sau egale cu '''1.000.000.000'''
== Exemplu 1 ==
; balin.txt
 3 3
 4 1 5
 2 6 3
; balout.txt
 Datele de intrare corespund restrictiilor impuse
 2
<br>
== Exemplu 2 ==
; balin.txt
 3 3
 4 11000000000 5
 2 6 3
; balout.txt
 Datele de intrare nu corespund restrictiilor impuse
<br>
== Explicatie ==
Sunt trei fete și trei băieți. Se pot forma doar două perechi: '''(1,2)''' și '''(4,6)'''
== Rezolvare ==
<syntaxhighlight lang="python" line>
def numar_maxim_perechi(n, m, fete, baieti):
    # Calculează numărul maxim de perechi de dansatori care se poate forma.

    fete.sort()
    baieti.sort()
    i = j = perechi = 0

    while i < n and j < m:
        if fete[i] <= baieti[j]:
            perechi += 1
            i += 1
        j += 1

    return perechi


def main():
    with open('balin.txt', 'r') as fin, open('balout.txt', 'w') as fout:
        n, m = map(int, fin.readline().split())
        fete = list(map(int, fin.readline().split()))
        baieti = list(map(int, fin.readline().split()))

        # Verifică dacă datele de intrare respectă restricțiile
        if not (1 <= n <= 100000 and 1 <= m <= 100000 and all(1 <= x <= 1000000000 for x in fete + baieti)):
            fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
            return

        fout.write("Datele de intrare corespund restrictiilor impuse\n")

        perechi = numar_maxim_perechi(n, m, fete, baieti)
        fout.write(f"{perechi}\n")


if __name__ == "__main__":
    main()


</syntaxhighlight>