Problema Bal,Campion 2009

2

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

Etichete:

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

2 Comentarii

  1. Andrei Misarca spune:
    noiembrie 13, 2009 la 7:59 pm

    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.

  2. Avadanei Andrei spune:
    noiembrie 13, 2009 la 8:44 pm

    Sincer nu stiam de aceasta denumire. 🙂 Am mai invatat un lucru nou cu ocazia asta! :))