C. Бөөнөөрөө зугтах

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хорон санаат хошин маягтай хүмүүсээс зугтахын тулд Малчин Жон фермээ орхисон ба Бовиниагийн өөр талруу аялахаар шийдсэн. Аялалын явцад тэр $k$ үнээтэйгээ хамт Гранд Мүү-дапест зочид буудалд буудаллахаар шийдсэн. Зочид буудал нь шугамын дагуу байрласан зарим нь эзэнтэй $n$ өрөөнөөс бүрдэнэ.

Малчин Жон түүнд болон түүний үнээнүүдэд зориулсан хүнгүй $k + 1$ өрөөний бүрдлийг захиалахыг хүсч байна. Тэр үнээнүүдээ боломжит хамгийн аюулгүй байлгахыг хүсч байгаа ба үнээний өрөөнөөс түүний өрөө хүртэлх хамгийн их зайг хамгийн бага байлгахыг хүсч байна. $i$ болон $j$ өрөөнүүдийн хоорондох зай нь $|j - i|$ байна. Малчин Жон үнээнүүдээ уг боломжит хамгийн бага зайг тооцоолох замаар хамгаалахад туслана уу.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ k < n ≤ 100 000$) байх ба буудлын өрөөний тоо болон Малчин Жонтой хамт яваа үнээнүүдийн тоо байна.

Хоёр дахь мөрөнд $n$ урттай тэмдэгт мөр байх ба өрөөнүүдийг тодорхойлно. Хэрвээ $i$-р өрөө чөлөөтэй байвал тэмдэгт мөрийн $i$-р тэмдэгт '$0$' байх бол хүнтэй байвал '$1$' байна. Энэ тэмдэгт мөрийн ядаж $k + 1$ тэмдэгт нь '$0$' байх нь тодорхой ба малчин Жон болон түүний үнээнүүд буудаллахад зориулсан $k + 1$ өрөөний ядаж нэг боломжит сонголт оршин байна.

Гаралт

Малчин Жоны өрөө болон түүний хамгийн хол байгаа үнээний өрөө хоорондын хамгийн бага зайг хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
7 2
0100100
Гаралт
2
Оролт
5 1
01010
Гаралт
2
Оролт
3 2
000
Гаралт
1

Тэмдэглэл

Эхний жишээн дээр малчин Жон $3$ өрөөг өөртөө ба $1$ болон $4$ өрөөг үнээнүүддээ захиалж чадна. Хамгийн хол байгаа үнээ хүртэлх зай $2$. Эзлэгдээгүй дараалласан гурван өрөө байхгүй учир уг зайг $1$ байлгах боломжгүй.

Хоёр дахь жишээн дээр малчин Жон $1$ өрөөг өөртөө болон $3$ өрөөг үнээндээ захиалж чадна. Жон болон үнээ хүртэлх зай $2$.

Гурав дахь жишээн дээр малчин Жон бүх боломжтой гурван өрөөг захиалах ба голын өрөөг өөртөө авах ба хоёр үнээ түүний хажуу талуудад байна. Хамгийн хол үнээ $1$ зайтай байна.

Сэтгэгдлүүдийг ачааллаж байна...