Programozás‎ > ‎Feladatok‎ > ‎

Istálló javítás

Egy viharos este a szél letépte János gazda istállóinak tetejét és kapuit. Szerencsére a tehenek egy része máshol tartózkodott, ezért az istálló nem volt teljesen tele. 

A tehenek egy-egy külön karámban töltik az estét, a karámok egy hosszú sorban egymás mellett helyezkednek el. Néhányban van tehén, néhányban nincs. Minden karám szélessége azonos.

János gazda a vihar után gyorsan megpróbálja bedeszkázni a karámokat, mert az ajtókat letépte a szél. E célból tetszőleges hosszúságú deszkákat tud rendelni, de csak néhány darabot. János szeretné elérni, hogy a megrendelt deszkák hosszának összege minimális legyen. 

Adott M (1 <= M <= 50), a rendelhető deszkák darabszámának maximuma; S (1 <= S <= 200), a karámok száma;  C (1 <= C <= S) a tehenek száma; és a C foglalt karám sorszáma (1 <= sorszám <= S). 

Feladat

Írjunk programot, ami megadja, hogy legkevesebb hány karám bedeszkázásával lehet kordában tartani a teheneket.

Bemenet

A bemenet első sora M, S és C értékét adja meg. Ezután C sorban egy-egy foglalt karám sorszáma következik.

Kimenet

A bedeszkázott karámok száma.

Példa

Bemenet  Kimenet
4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43
25


Például: 3-8, 14-21, 25-31 és 40-43.

Tesztadatok

Címkék

A feladat forrása: USACO training material, Barn Repair
Algoritmusok: 

megoldás