Hide

Veggja Kalli

/problems/iceland.veggjakalli/file/statement/is/img-0001.jpg
Mynd fengin af pixabay.com

Kalli er mikill smiður sem hefur einstaklega mikinn áhuga á veggjum. Í dag fékk Kalli verkefni. Verið er að búa til nýja íbúð sem er gefin með $N$ stökum. Hvert stak táknar reit sem er annaðhvort veggur táknaður með # eða opinn reitur táknaðar með -. Gefið er að vinstrasti og hægrasti reitir eru alltaf veggir.

Kalli var beðinn um að brjóta niður minnsta fjölda veggja þannig það væri til herbergi sem hefur stærð nákvæmlega $M$. Það er að segja, að það séu nákvæmlega $M$ opnir reitir hlið við hlið, hvorki meira né minna. Kalli má ekki brjóta veggina vinstrast eða hægrast því þá er opið út.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $N$ og $M$ ($1 \leq M \leq N \leq 5\cdot 10^5$), fjöldi reita og stærðina á herberginu sem Kalli á að búa til.

Næsta lína inniheldur streng með $N$ stöfum, sem lýsir íbúðinni.

Úttak

Skrifa skal út eina línu með minnsta fjölda veggja sem Kalli þarf að brjóta niður þannig krafan að ofan sé uppfyllt. Ef það er ekki hægt þá skal skrifa út Neibb.

Stigagjöf

Hópur

Stig

Takmarkanir

1

28

$N \leq 100$

2

32

$N \leq 3\, 000$

3

40

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
7 2
#-#-#-#
Neibb
Sample Input 2 Sample Output 2
8 3
#-###--#
1
Sample Input 3 Sample Output 3
4 3
#--#
Neibb
CPU Time limit 1 second
Memory limit 1024 MB
Author
Bernhard Linn Hilmarsson
Source Forritunarkeppni Framhaldsskólanna 2020
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in