Fişierul intrare/ieşire:mafioti.in, mafioti.outSursăLot Baia Mare 2013 - Baraj 3 Seniori
AutorAdrian Budau, Andrei GrigoreanAdăugată deMagnvsDaniel Constantin Anghel Magnvs
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.inmafioti.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content