A. Ээлжлэх ухаан

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

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

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

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

Кевин саяхан Америкийн нэгдсэн улсын үнээ тогтоох олимпиадын (USAICO) дүнгээ $n$ урттай хоёртын тооллын системийн тэмдэгт мөр хэлбэрээр хүлээж авсан. Кевиний тэмдэгт мөрийн тэмдэгт бүр олимпиадын $n$ асуултуудын нэгэн дээр нь Кевиний авсан оноог илэрхийлэх буюу үнээг зөв тогтоосон бол $'1'$ бусад тохиолдолд $'0'$ байна.

Гэсэн хэдий ч бүх зүйл дуусчихаагүй байна. Кевин бол ээлжлэх ухааны том дэмжигч ба түүний оноо түүний нийт оноонуудын нийлбэр биш түүний тэмдэгт мөрт байгаа хамгийн урт ээлжлэх дэд дарааллийн урт байх ёстой гэдэгт итгэдэг. Энд бид тэмдэгт мөрийн ээлжлэх дэд дарааллийг ямар ч хоёр дараалласан элемент нь тэнцүү биш зэргэлдээ орших шаардлагагүй дэд дараалал хэлбэрээр тодорхойлно. Жишээлбэл ${0, 1, 0, 1}$ ба ${1, 0, 1}$ болон ${1, 0, 1, 0}$ нь ээлжлэх дарааллууд боловч ${1, 0, 0}$ болон ${0, 1, 0, 1, 1}$ нь биш юм.

Кевин борооны дараах жижиг мөөг шиг зальжин байж USAICO-н өгөгдлийн санруу халдаж өөрийн оноог өсгөхийг хүссэн. Анзаарагдахгүйн тулд тэр яг нэг дэд тэмдэгт мөрийг урвуу болгохоор шийдсэн буюу өөрийн онооныхоо зэргэлдээ хоосон биш дэд тэмдэгт мөрийг авч бүх $'0'$-г $'1'$-р харин эсрэгээрээ бүх $'1'$-г $'0'$-р солихоор шийдсэн. Ийм үйлдлийнхээ дараа түүний тэмдэгт мөрөнд байх боломжтой боломжит хамгийн урт ээлжлэх дэд дарааллийн уртыг мэдэхийг хүссэн.

Оролт

Эхний мөрөнд олимпиадын асуултуудын тоо $n$ ($1 ≤ n ≤ 100 000$) байна.

Дараагийн мөрөнд Кевиний USAICO-н хариуг илтгэх $n$ урттай хоёртын тэмдэгт мөр байна.

Гаралт

Кевин тэмдэгт мөрийнхөө нэг дэд тэмдэгт мөрийг урвуу болгох замаар үүсгэж чадах боломжит хамгийн урт ээлжлэх дэд дарааллийн уртыг илэрхийлэх нэг ширхэг бүхэл тоон утгыг хэвлэ.

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

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

Оролт
8
10000011
Гаралт
5
Оролт
2
01
Гаралт
2

Тэмдэглэл

Эхний жишээн дээр Кевин харлуулсан '100$00$011' дэд тэмдэгт мөрийг урвуу болгох ба түүний тэмдэгт мөр '$10011011$' болж ээлжлэх дэд тэмдэгт мөрний урт нь 5: '$1$0$01$1$01$1$'.

Хоёр дахь жишээн дээр Кевин тэмдэгт мөрийг бүхлээр нь урвуу болгож болох ба ижил оноотой байна.

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