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] ⩽ b[j].

Restricţii şi precizări

• 1 ⩽ n, m ⩽ 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

Exemplu 2

balin.txt

3 3
4 11000000000 5
2 6 3

balout.txt

Datele de intrare nu corespund restrictiilor impuse

Explicatie

Sunt trei fete și trei băieți. Se pot forma doar două perechi: (1,2) și (4,6)

Rezolvare

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()