.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » granita

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
granita


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

La granita statului A cu statul B se afla N dispozitive de aparare. Pentru fiecare dispozitiv k se cunoaste intervalul de lungime [Ak,Bk] în care actioneaza (granita se considera a fi o linie dreapta, iar fiecare dispozitiv acopera un anumit segment de pe aceasta linie). Pentru a reduce costurile de întretinere, presedintele statului A a decis ca unele dintre cele N dispozitive de aparare sa fie desfiintate. Mai precis, vor fi desfiintate dispozitivele redundante. Un dispozitiv i este redundant, daca exista cel putin un alt dispozitiv j, astfel încât intervalul [Ai,Bi] sa fie inclus în intervalul [Aj,Bj] (adica Aj<Ai si Bi<Bj).

Cerinta

Determinati câte dintre cele N dispozitive de aparare sunt redundante.

Date de intrare

Pe prima linie a fisierului de intrare granita.in se afla numarul întreg N, reprezentând numarul dispozitivelor de aparare. Pe urmatoarele N linii se afla câte doua numere întregi, A si B (A<B), reprezentând capetele intervalelor în care actioneaza fiecare dispozitiv.

Date de iesire

În fisierul de iesire granita.out contine o singura linie pe care veti afisa un singur numar întreg, reprezentând numarul dispozitivelor redundante.

Restrictii

  • 1<= N <= 16 000
  • 0 <= Ai < Bi <= 2 000 000 000
  • Toate numerele Ai vor fi diferite între ele.
  • Toate numerele Bi vor fi diferite între ele.

Exemple

granita.in granita.out
5
0 10
2 9
3 8
1 15
6 11
3

Explicatie

Dispozitivele redundante sunt: al doilea, al treilea si al cincilea.

Mugurel Ionut Andreica
Universitatea Politehnica Bucuresti

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, soricel1, traseu, zapezi, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, sediu, soricel3, ferma, fni, sah1, suma3, nr4, fractie, blockout, join, cod3, tunel, lover, trip, pepsi, string, medii, transport, tren3, avion, prime1, poligon1, monkey, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, cafea, top, echipe1, zoo, secvente
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, jobs, senzori, echipe, agitatie, center, algebra, tgraf, bcast, promo, asmax, sediu, string, poligon1, csir, lsort, zoo, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, ic, xp, v2d, ppcover, carray, asfalt1, module, gxor
Despre heap: sirag, hperm, gard, pitici1, cezar1, munte2, base3, sea, oldest, ksecv
Despre sortare: harta, index, sort, concurs, baby, patrate2, repeat, turist, bacan, toys, scor2, chimie2, politics, submat, scoici, ham, jokes, trecere, multiplu, paralel, tvshow, sirag1, tabara, munte, sport, puncte1, sume1, schi, tren3, sant1, volei1, poze, maroco, dreptc, dist1, tir1, control, mosia, popas, reactivi, siruri1, coach, anag, matrice4, sume2, urgenta, basm, vot, balcon, joc14, cerc, k1, segm, calorii, ordonare, greutati, arctir, macheta, poligon4, centrala, robot4, lcdr, maxviz, sdmin, qtri, arme, flori1, parc1, mijloc, bile6, proiecte, patru, drept2, subsecvente, cursa1, eoliene, vintage, dreapta, riglef, rebus1, rascoala, zimeria, praslea, aperm, unudoi, gropi1, piscina, restaurare, cabana, culori3
surse trimise | ajutor