E. 2 дэд дараалал

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

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

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

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

IT-ын хичээл дээр Валера өгөгдлийн шахалтыг сурчээ. Багш нь түүнд бид одоо танд тайлбарлах шинэ аргын тухай хэлжээ.

${a_{1}, a_{2}, ..., a_{n}}$ нь шахагдах хэрэгтэй өгөгдсөн тэмдэгтүүдийн дараалал юм. Энд ба доор бид бүх ижил урттай тэмдэгтүүд нь зөвхөн $0$ болон $1$ цифрүүдээс тогтоно гэж үзнэ. Одоо шахалтын функцийг тодорхойлъё:

  • $f$(хоосон дараалал) = хоосон тэмдэгт мөр
  • $f(s) = s$.
  • $f(s_{1}, s_{2}) =$  нэг угтвар нь $s_{1}$-тай тэнцүү байх ба нэг дагавар нь $s_{2}$-тай тэнцүү байх хамгийн бага урттай тэмдэгт мөр байна. Жишээлбэл, $f(001, 011) = 0011$, $f(111, 011) = 111011$.
  • $f(a_{1}, a_{2}, ..., a_{n}) = f(f(a_{1}, a_{2}, a_{n - 1}), a_{n})$. Жишээлбэл, $f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111$.

Валера одоо жинхэнэ сорилттой тулгарчээ: Тэрээр өгөгдсөн ${a_{1}, a_{2}, ..., a_{n}}$ дарааллыг ${b_{1}, b_{2}, ..., b_{k}}$ болон ${c_{1}, c_{2}, ..., c_{m}}$, $m + k = n$ гэсэн 2 дэд дараалалд хуваах ёстой ба ингэснээр $S = |f(b_{1}, b_{2}, ..., b_{k})| + |f(c_{1}, c_{2}, ..., c_{m})|$ -ын утга нь боломжит хамгийн бага байх ёстой юм. Энд $|p|$-ээр $p$ тэмдэгт мөрийн уртыг тэмдэглэв.

Дэд дарааллуудын доторх тэмдэгтүүдийн харьцангуй дарааллыг өөрчлөх нь зөвшөөрөгдөөгүй болохыг анхаарна уу. Дэд дарааллуудын нэгийг нь хоосон байлгах нь зөвшөөрөгдсөн. Анхны дарааллын тэмдэгт болгон нь заавал нэг дэд дараалалд харьяалагдах ёстой. $b$ болон $c$ дэд дарааллуудын элементүүд нь анхны дараалал $a$-д заавал дараалсан байх албагүй, өөрөөр хэлбэл $b$ болон $c$-ын элементүүд нь $a$-д сэлгэсэн байж болно (2 болон 3-дахь жишээг харна уу).

Валера-д $S$-ын боломжит хамгийн бага утгыг олоход тусална уу.

Оролт

Оролтын эхний мөрөнд бүхэл тоо $n$ өгөгдөнө -- энэ нь тэмдэгтүүдийн тоог илэрхийлнэ ($1 ≤ n ≤ 2*10^{5}$). Дараа нь $n$ мөрөнд дарааллын дараах элементүүд өгөгдөнө -- $1$-ээс $20$ хүртэлх тэмдэгтийн урттай зөвхөн $0$ болон $1$ цифрүүдээс тогтох тэмдэгтүүд байна. Оролтын $i + 1$-дахь мөрөнд дарааллын $i$-дахь элемент өгөгдөнө. Дарааллын элементүүд нь зөвхөн нэг шинэ мөрөөр тусгаарлагдана. Мөн бүх мөрүүд нь ижил урттай байна.

Гаралт

$S$-ын боломжит хамгийн бага утгыг илэрхийлэх ганц тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3
01
10
01
Гаралт
4
Оролт
4
000
111
110
001
Гаралт
8
Оролт
5
10101
01010
11111
01000
10010
Гаралт
17

Тэмдэглэл

Сорилтуудын нарийвчилсан хариултууд:

  • Хамгийн зөв сонголт нь нэг дэд дарааллыг хоосон үлдээх ба 2-дахь нь бүхэл бүтэн өгөгдсөн дараалалтай тэнцүү байна. $|f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4$.
  • Хамгийн зөв сонголт нь: $b = {000, 001}, c = {111, 110}.$ $S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8$.
  • Хамгийн зөв сонголт нь: $b = {10101, 01010, 01000}, c = {11111, 10010}.$ $S = |10101000| + |111110010| = 17$.
Сэтгэгдлүүдийг ачааллаж байна...