ŠKOLSKO NATJECANJE 2015. / Srednja škola, II. podskupina (3. i 4. razred) - 3. zadatak

Na parkiralište stane P automobila parkiranih jedan do drugoga, svi u jednom redu.

Trenutna popunjenost parkirališta je zadana nizom znakova, gdje znak ‘#’ (ljestve) označava zauzeto parkirno mjesto, a znak ‘.’ (točka) označava slobodno mjesto.

Uskoro dolazi K velikih kamiona od kojih svaki zauzima točno L uzastopnih parkirnih mjesta te je potrebno ukloniti neke parkirane automobile s parkirališta kako bi bilo moguće parkirati sve kamione na slobodna mjesta.

Kamioni ne moraju biti parkirani na susjedna mjesta.

Napišite program koji za zadano parkiralište određuje koliko je najmanje automobila potrebno ukloniti kako bi bilo moguće parkirati sve kamione.

Ulazni​ podaci

U prvom redu nalaze se tri prirodna broja, P, K i L (P, K, L ≤ 1000) međusobno odvojena razmakom - broj parkirnih mjesta, broj kamiona i broj parkirnih mjesta koje svaki kamion zauzima.

U drugom redu nalazi se točno P znakova koji predstavljaju popunjenost parkinga.

Svaki znak je točka ‘.’ ili ljestve ‘#’.

Ulazni podaci će uvijek biti takvi da će biti moguće parkirati sve kamione, tj. vrijedit će K*L ≤ P.

Izlazni podaci

U prvi i jedini red potrebno je ispisati koliko je najmanje automobila potrebno ukloniti.

Primjeri test​ podataka

Ulaz

6 1 3
#.#.##

Izlaz

1

Ulaz

9 2 3
.##..#..#

Izlaz

2

Ulaz

15 2 5
.#.....#.#####.

Izlaz

3

Objašnjenje

Objašnjenje 3. primjera: Ako uklonimo prva tri automobila sa lijeve strane, dobivamo 10 slobodnih

parkirnih mjesta na kojih možemo parkirati dva kamiona duljine 5.