== include(page="template/taskheader" task_id="mafioti") ==
Poveste şi cerinţă...
M mafioţi au pus stăpânire peste oraşul Grozburg. Acesta este reprezentat sub forma axei Ox a sistemului de coordonate, la fiecare coordonată întreagă pozitivă aflându-se câte o cladire. Se ştie că dintre toate clădirile oraşului, N sunt bănci unde mafioţii îşi pot depunde câştigurile ilegale. Fiecare mafiot îşi poate folosi influenţa pentru a obţine controlul a unui interval de fix K clădiri consecutive ale oraşului. Pentru a nu stârni suspiciunile DIICOT, mafioţii doresc ca un număr minim de clădiri din oraş să se afle sub influenţa acestora. O clădire este considerată ca fiind sub influenţa mafioţilor dacă este sub influenţa a cel puţin unuia dintre ei.
Mafioţii trebuie să îşi aleagă intervalele de clădiri (nu neapărat disjuncte) astfel încât fiecare să îşi poată alege o bancă din intervalul său pe care o va folosi pentru a îşi depunde câştigurile sale. Doi mafioţi nu îşi pot alege aceeaşi bancă pentru depunerea câştigurilor, chiar dacă banca se află în intervalele amândurora. Pentru ca cei M mafioţi să convieţuiască în linişte, fiecare trebuie să aibă banca sa proprie.
Voi trebuie să alegeţi intervalele de influenţă ale fiecărui mafiot astfel încât să se respecte restricţiile de mai sus şi un număr minim de clădiri să fie sub influenţa acestora.
h2. Date de intrare
Fişierul de intrare $mafioti.in$ ...
Pe prima linie a fişierului mafioti.in se află N, M şi K, numărul de bănci din oraş, numărul de mafioţi, respectiv lungimea intervalului de influenţă. Următoarea linie conţine N numere întregi pozitive şi distincte, al i-lea din aceste numere reprezentând coordonata celei de-a i-a bănci.
h2. Date de ieşire
În fişierul de ieşire $mafioti.out$ ...
Pe prima (şi singura) linie a fişierului mafioti.out trebuie să afişaţi numărul minim de clădiri de sub influenţa mafioţilor astfel încât să fie respectate regulile de mai sus.
h2. Restricţii
* $... ≤ ... ≤ ...$
1 <= N <= 5.000
1 <= M <= 1.000
1 <= K <= 1.000.000.000
Coordonatele cladirilor se afla in intervalul [1, 1.000.000.000]
Pentru 40% din teste N <= 500
h2. Exemplu
table(example). |_. mafioti.in |_. mafioti.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 4 4
1 3 4 5 7 8
| 5
|
h3. Explicaţie
...
Primul mafiot alege clădirile 1, 2, 3, 4 (controlează banca 1). Al doilea alege clădirile 1, 2, 3, 4 (controlează banca 3). Al treilea alege clădirile 2, 3, 4, 5 (controlează banca 4). Al patrulea alege clădirile 2, 3, 4, 5 (controlează banca 5). În total mafioţii controlează un minimum de 5 clădiri.
== include(page="template/taskfooter" task_id="mafioti") ==
== include(page="template/taskfooter" task_id="mafioti") ==
