Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cuplaje.in, cuplaje.out | Sursă | Algoritmiada 2016 Runda 3 Seniori |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cuplaje
Se spune ca in general dragostea e oarba. In cazul de fata in schimb nu este asa: dragostea este sistematica si bine definita din punct de vedere matematic. Mai exact, avem N baieti numerotati de la 1 la N. Acestia sunt ordonati dupa cat de bogati sunt ei ( 1 este cel mai bogat, N este cel mai sarac). De asemenea, avem M fete numerotate de la 1 la M. Acestea sunt ordonate dupa cat de frumoase sunt ( 1 este cea mai frumoasa, M este cea mai ur.... mai putin frumoasa).
Fiecare baiat respectiv fata au desigur preferintele lor, dar acestea determina o relatie de ordine foarte simpla. Daca un baiat este dispus sa se cupleze cu o fata X, atunci acesta este dispus sa se cupleze cu orice fata mai frumoasa ca ea (orice alta fata Y ≤ X). Asemanator, daca o fata este dispusa sa se cupleze cu un baiat X, atunci aceasta este dispusa sa se cupleze cu orice baiat mai bogat ca acesta (orice alt baiat Y ≤ X).
Dandu-se pentru fiecare baiat, respectiv fata, care este cea mai slaba preferinta cu care ar fi de acord sa se cupleze, sa se determine numarul maxim de cuplari ce pot fi realizate intre cei N baieti si M fete, ştiind că fiecare băiat, respectiv fată poate fi implicat/implicată într-un singur cuplu.
Date de intrare
Fişierul de intrare cuplaje.in va conţine pe prima sa linie numerele N şi M. A doua linie va conţine N numere, reprezentând preferinţa "worst-case" a fiecărui băiat. A treia linie va conţine M numere, reprezentând preferinţa "worst-case" a unei fete.
Date de ieşire
În fişierul de ieşire cuplaje.out se va afla un singur număr, reprezentând numărul maxim de cupluri care se pot forma.
Restricţii
- 1 ≤ N, M ≤ 200.000
- Elementele din primul şir au valori între 1 şi M, iar cele din al doilea şir au valori între 1 şi N.
- Acest enunţ este un pamflet şi nu reflectă opinia noastră despre băieţi, fete, bogăţie sau frumuseţe.
Exemplu
| cuplaje.in | cuplaje.out |
|---|---|
| 3 4 2 3 1 3 1 1 1 | 2 |
Explicaţie
Primul băiat este de acord cu oricare din primele două fete. Al doilea băiat este de acord cu orice fată, iar al treilea (deşi cel mai puţin bogat) este de acord să se cupleze doar cu prima fată. Se pot face două cupluri: prima fată cu al doilea băiat, respectiv a doua fată cu primul băiat. Nu putem obţine un număr mai mare de cupluri, deoarece cu excepţia celei mai frumoase fete, restul sunt destul de pretenţioase.
