B. Баавгай ба Гэмт хэрэгтнүүдийг барих

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

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

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

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

Берланд $1$-с $n$ хүртэл дугаарлагдсан $n$ хоттой. Хотууд мөрийн дагуу цуварч байрласан. $i$ болон $j$ дугаартай хотуудын хоорондох зай $|i - j|$.

Лимак бол цагдаагийн офицер. Тэр $a$ хотод амьдардаг. Тэр гэмт хэрэгтнүүдийг барих ажилтай. Лимак аль хотуудад гэмт хэрэгтнүүд байгааг мэдэхгүй учир тэднийг барих нь төвөгтэй. Гэвч тэр хот бүрт хамгийн ихдээ нэг гэмт хэрэгтэн байгаа гэдгийг мэдэж байгаа.

Лимак ГХБИ (Гэмт Хэрэгтэн Баавгайг Илрүүлэгч) ашиглах гэж байна. ГХБИ нь Лимакд $a$ хотоос тодорхой зай бүрт хэдэн гэмт хэрэгтэн байгааг хэлж өгөх болно. Үүний дараа Лимак гэмт хэрэгтэн байгаа хот бүр дэх гэмт хэрэгтнийг барьж чадна.

Та гэмт хэрэгтэнтэй хотуудыг мэдэж байгаа. Лимак ГХБИ-г ашигласнийхаа дараа барьж чадах гэмт хэрэгтнүүдийн тоог тоол.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $a$ ($1 ≤ a ≤ n ≤ 100$) байх ба хотуудын тоо болон Лимакын амьдардаг хотын дугаар байна.

Хоёр дахь мөрөнд $n$ бүхэл тоон утга $t_{1}, t_{2}, ..., t_{n}$ ($0 ≤ t_{i} ≤ 1$) байна. $i$-р хотод $t_{i}$ гэмт хэрэгтэн байгаа.

Гаралт

Лимакын барих гэмт хэрэгтнүүдийн тоог хэвлэ.

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

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

Оролт
6 3
1 1 1 0 1 0
Гаралт
3
Оролт
5 2
0 0 0 1 0
Гаралт
1

Тэмдэглэл

Эхний жишээн дээр зургаан хот байгаа ба Лимак гуравдугаар хотод (доороо хөх сумтай) амьдардаг. Гэмт хэрэгтнүүд улаанаар тэмдэглэгдсэн хотуудад байгаа.

ГХБИ-г ашигласнаар Лимак дараах мэдээлэлтэй болно:

  • Гуравдугаар хотоос $0$ зайд нэг гэмт хэрэгтэн байгаа ба Лимак уг гэмт хэрэгтэн яг гуравдугаар хотод байгаа гэдэгт итгэлтэй байна.
  • Гуравдугаар хотоос $1$ зайд нэг гэмт хэрэгтэн байгаа ба Лимак уг гэмт хэрэгтэн хоёр эсвэл дөрөвдүгээр хотын алинд байгааг нь мэдэхгүй.
  • Гуравдугаар хотоос $2$ зайд хоёр гэмт хэрэгтэн байгаа ба Лимак нэг болон тавдугаар хотод нэг нэг гэмт хэрэгтэн байгаа гэдэгт итгэлтэй байна.
  • Үүнээс хол зайд нэг ч гэмт хэрэгтэн байхгүй.

Ингээд Лимак $1$, $3$ ба $5$ хотууд дахь гэмт хэрэгтнүүдийг барих ба нийт $3$ гэмт хэрэгтэн барина.

Хоёр дахь жишээн дээр (доор зурсан) ГХБИ Лимакд түүний амьдарч буй хотоос $2$ зайд нэг гэмт хэрэгтэн байна гэсэн мэдээлэл өгнө. $2$ зайд ганцхан хот байгаа учир Лимак гэмт хэрэгтнийг хаана байгааг баттай мэднэ.

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