Revizia anterioară Revizia următoare
Fișierul intrare/ieșire | acoperire.in, acoperire.out | Sursă | ad-hoc |
---|---|---|---|
Autor | din folclor | Adăugată de | Andrei Nae • andreins |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Acoperire
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.
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
- 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,20],[23,27],[25,34].