#699
Se consideră N
intervale [Ai,Bi]
, 1 ≤ i ≤ N
disjuncte.
Tuturor intervalelor li se aplică o operație de extindere la ambele capete cu o valoare naturală x
, astfel încât după extindere cu valoarea x
, intervalul [Ai,Bi]
va deveni intervalul [Ai-x,Bi+x]
, 1 ≤ i ≤ N
.
După extindere, spunem că intervalele [Ai,Bi]
și [Aj,Bj]
aparțin aceluiași grup de intervale dacă ele se intersectează sau dacă există un interval [Ak,Bk]
astfel încât [Ai,Bi]
se intersectează cu [Ak,Bk]
iar intervalele [Ak,Bk]
, [Aj,Bj
] aparțin aceluiași grup de intervale.
Să se determine valoarea minimă x
cu care vor trebui să fie extinse toate intervalele astfel încât să se formeze un grup cu cel puțin P
intervale.
Lot Juniori, Deva, 2013