Atenție! Aceasta este o versiune veche a paginii., scrisă la 2012-11-29 16:51:44.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire acoperire.in, acoperire.out Sursă ad-hoc
Autor din folclor Adăugată de avatar andreins Andrei Nae andreins
Timp de execuție pe test 0.1 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

table(example). |_. acoperire.in |_. acoperire.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii