Problem J
Veggja Kalli
Languages
en
is
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 |
