==Include(page="template/taskheader" task_id="granita")==
== include(page="template/taskheader" task_id="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~}$).
Poveste ...
h2. Cerinta
Determinati cate dintre cele $N$ dispozitive de aparare sunt redundante.
...
h2. Date de Intrare
h2. Restrictii
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.
...
h2. Date de Iesire
h2. Date de intrare
In fisierul de iesire $granita.out$ contine o singura linie pe care veti afisa un singur numar intreg, reprezentand numarul dispozitivelor redundante.
...
h2. Restrictii
h2. Date de iesire
* $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
h2. Exemple
table(example). |_. granita.in |_. granita.out |
|5
0 10
2 9
3 8
1 15
6 11 | 3 |
...
h3. Explicatie
h2. Exemplu
Dispozitivele redundante sunt: al doilea, al treilea si al cincilea.
| granita.in | granita.out |
| linia1
linia2
linia3
| linia1
linia2
|
==Include(page="template/taskfooter" task_id="granita")==
== include(page="template/taskfooter" task_id="granita") ==
