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

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