Diferențe pentru problema/acoperire între reviziile #10 si #4

Acoperire

acoperire

== include(page="template/taskheader" task_id="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]$.

Scrieti un program care calculeaza si afiseaza numarul minim de alegere a N intervale deschise pentru ca prin reuniunea acestora intervalul dat (A,B) sa fie inclus.

h2. 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$.

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.

h2. Date de ieșire

h2. Restricții

* $1 ≤ N ≤ 1000$

* N ≤ 1000

* $1 ≤ A,B ≤ 10000$
* $1 ≤ A1,B1 ≤ 20000$

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

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

| 4
|
h3. Explicație

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

Putem alege intervalele (13,20),(17,20),(23,27),(25,34).

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