Problema Bal,Campion 2009
2Un grup de fete si baieti participa la balul bobocilor. Ca sa evite aglomeratia de pe ringul de dans, organizatorii au realizat o programare in care fiecarui participant i se aloca o perioada de timp in care se va afla pe ringul de dans.
Cerinta
Scrieti un program care sa determine numarul maxim de perechi, fata-baiat, care se pot forma cu persoanele aflate pe ringul de dans la un moment dat.
Date de intrare
Fisierul de intrare bal.in contine pe prima linie numerele naturale n si m reprezentand numarul de fete si numarul de baieti participanti la bal. Pe urmatoarele n linii se gasesc cate doua numere naturale xi yi, (1<=i<=n) separate printr-un spatiu reprezentand intervalul inchis de timp in care se va afla pe ring fiecare fata. Pe urmatoarele m linii se gasesc cate doua numere naturale xj yj, (1<=j<=m) separate printr-un spatiu reprezentand intervalul inchis de timp in care se va afla pe ring fiecare baiat.
Date de iesire
Fisierul de iesire bal.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul maxim de perechi determinat.
Restrictii
- 1 <= n <= 100 000
- 1 <= m <= 100 000
- 1 <= xi <= yi <= 1 000 000
- 1 <= xj <= yj <= 1 000 000
Exemple
bal.in | bal.out |
3 3 11 16 1 8 6 9 4 20 8 17 13 18 |
2 |
Solutia mea
O abordare foarte draguta a problemei consta in crearea a doi vectori sugestivi(B – baieti si F – fete) astfel : pentru fiecare xi,yi (intervalul in care un copil sta pe scena : baiat/fata) B[xi]++,B[yi]– respectiv F[xi]++,F[yi]–. Cu ajutorul unei parcurgeri pana la MAX_N vom avea la fiecare moment numarul de baieti si fete de pe scena (initial fiind 0,adaugam sau scadem in functie de B[pasi]/F[pasi].
Inseamna ca MAX(pasi) = MAX(MAX(pasi-1),MIN(B[pasi],F[pasi]));
Descarcati solutia pentru problema Bal de la Campion 2009.
Se mai numeste smenul lui Mars ce ai facut aici. Mi s-au parut marfa problemele de la grupa M, spre deosebire de cele de la L care mi s-au parut niste porcarii.
Sincer nu stiam de aceasta denumire. 🙂 Am mai invatat un lucru nou cu ocazia asta! :))