carpetbomber

Carpet Bomber

Ato Marm şi-a adus aminte de vremurile în care juca $C&C Generals$. $Carpet Bombing$ a fost o tehnică utilizată de către generalii chinezi în războiul împotriva GLA. O salvă de bombe era eliberată de către o aeronavă puternică, de obicei un $B-52$ asupra unei zone alese de general, producând pagube semnificative. Bombardierele mentineau o traiectorie liniara si de aceea erau foarte eficiente la oprirea transporturilor ce mergeau pe sosele.

Generalul chinez Tsing Shi Tao are ordine sa bombardeze intreaga suprafata a unei autostrazi liniare. Aceasta autostrada este impartite in $1 000 000$ de intervale de lungime $1$. Acesta are la dispozitie $N$ aeronave, fiecare dintre ele avand explozibil de tipul $T{~i~}$ si un interval continuu $[L{~i~}, R{~i~}]$ pe care aceasta il bombardeaza in cazul in care este folosit. El are de asemenea ordine sa foloseasca aeronave cu maxim $2$ tipuri diferite de explozibil pentru bombardarea autostarzii. Se cere aflarea numarului minim de aeronave necesare bombardarii intregii autostrazi, in cazul in care acest lucru este posibil. In cazul in care nu se poate bombarda intreaga autostrada, afisati $-1$.

Generalul chinez Tsing Shi Tao are ordine sa bombardeze intreaga suprafata a unei autostrazi liniare. Aceasta autostrada este impartita in $1 000 000$ de intervale de lungime $1$ numerotate de la $1$ la $1 000 000$. Generalul are la dispozitie $N$ aeronave, fiecare dintre ele avand explozibil de tipul $T{~i~}$ si un interval continuu din autostrada $[L{~i~}, R{~i~}]$ pe care aceasta il bombardeaza in cazul in care este folosita. El are de asemenea ordine sa foloseasca aeronave cu maxim $2$ tipuri diferite de explozibil. Se cere aflarea numarului minim de aeronave necesare bombardarii intregii autostrazi, in cazul in care acest lucru este posibil. In cazul in care nu se poate bombarda intreaga autostrada, afisati $-1$.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $carpetbomber.out$ ...

În fişierul de ieşire $carpetbomber.out$ prima linie va contine numarul minim de aeronave necesare bombardarii, respectand in acelasi timp restrictia mentionata sau $-1$ daca acoperirea intregii autostrazi nu este posibila.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 8 191$
* $1 ≤ T{~i~} ≤ 1 023$
* $1 ≤ L{~i~} ≤ R{~i~} ≤ 1 000 000$

h2. Exemplu
table(example). |_. carpetbomber.in |_. carpetbomber.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
1 1 250000
2 250001 500000
1 750001 1000000
3 500001 1000000
2 500001 750000
| 4

|
h3. Explicaţie

...

Se vor folosi bombele cu numerele de ordine $1$, $2$, $3$ si $5$.
Daca am putea folosi bombe cu mai mult de $2$ tipuri de explozibil am folosi bombele cu numerele de ordine $1$, $2$ si $4$ pentru a bombarda intreaga autostrada.

== include(page="template/taskfooter" task_id="carpetbomber") ==

3890