Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | granita.in, granita.out | Sursă | .campion 2003 |
| Autor | Mugurel Ionut Andreica | Adăugată de | |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Vezi solutiile trimise | Statistici
Granita
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
Granita
La granita statului A cu statul B se afla N dispozitive de aparare. Pentru fiecare dispozitiv k se cunoaste intervalul de lungime [A[k], B[k]] in 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 intretinere, 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 incat intervalul [A[i], B[i]] sa fie inclus in intervalul [A[j], B[j]] (adica A[j]<A[i] si B[i]<B[j]).
Cerinta
Determinati cate dintre cele N dispozitive de aparare sunt redundante.
Date de Intrare
Pe prima linie a fisierului de intrare granita.in se afla numarul intreg N, reprezentand numarul dispozitivelor de aparare. Pe urmatoarele N linii se afla cate doua numere intregi, a si b (a<b), reprezentand capetele intervalelor in care actioneaza fiecare dispozitiv.
Date de Iesire
In fisierul de iesire granita.out contine o singura linie pe care veti afisa un singur numar intreg, reprezentand numarul dispozitivelor redundante.
Restrictii
. 1 <= N <= 16.000
. 0 <= A[i] < B[i] <= 2.000.000.000
. Toate numerele A[i] vor fi diferite intre ele
. Toate numerele B[i] vor fi diferite intre ele
Exemple
| granita.in | granita.out |
| 5 | 3 |
| 0 10 | |
| 2 9 | |
| 3 8 | |
| 1 15 | |
| 6 11 | |
Explicatie:
Dispozitivele redundante sunt: al doilea, al treilea si al cincilea.
