| Fişierul intrare/ieşire: | mafioti.in, mafioti.out | Sursă | Lot Baia Mare 2013 - Baraj 3 Seniori |
| Autor | Adrian Budau, Andrei Grigorean | Adăugată de |  Daniel Constantin Anghel •Magnvs |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mafioti
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.
Date de intrare
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.
Date de ieşire
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.
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
Exemplu
| mafioti.in | mafioti.out |
|---|---|
| 6 4 4 1 3 4 5 7 8 | 5 |
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.
