Fişierul intrare/ieşire:acoperire.in, acoperire.outSursăad-hoc
AutorDin FolclorAdăugată deandreinsAndrei Nae andreins
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Acoperire

Avem la dispozitie un interval inchis [A,B] si o multime de alte N intervale inchise [Ai,Bi], 1 ≤ i ≤ N. Scrieti un program care calculeaza si afiseaza numarul minim de intervale inchise din multimea data cu proprietatea ca prin reuniunea acestora se obtine un interval care include pe [A,B].

Date de intrare

Fişierul de intrare acoperire.in contine pe prima linie intervalul care va trebui sa fie inclus in reuniune. Pe urmatoarea linie avem numarul N, reprezentand numarul de intervale date, iar pe urmatoarele N linii avem intervalele de forma [Ai,Bi]. Daca prin reuniunea tuturor intervalelor nu putem obtine un interval care sa includa intervalul [A,B], se va afisa -1.

Date de ieşire

În fişierul de ieşire acoperire.out vom avea numarul minim de intervale ce trebuie alese pentru a satisface cerinta.

Restricţii

  • 1 ≤ N ≤ 1000
  • 1 ≤ A,B ≤ 10000
  • 1 ≤ A1,B1 ≤ 20000

Exemplu

acoperire.inacoperire.out

13 28
9
1 12
3 20
15 19
25 34
17 23
24 25
13 20
11 16
23 27

4

Explicaţie

Putem alege intervalele [13,20],[17,23],[23,27],[25,34].

Trebuie sa te autentifici pentru a trimite solutii. Click aici