Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Хамминг зайн нийлбэр
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Жино-д таны тусламж хэрэг болжээ.Тэрээр дараах програмчлалын бодлогыг Сайтама-д бодуулахаар өгчээ:
Зарим нэг $s$ тэмдэгт мөрийн уртыг $|s|$ гэж тэмдэглэе.Ижил урт бүхий $s$ болон $t$ тэмдэгтүүдийн хоорондох Хамминг зай гэдэг нь гэж тодорхойлогдох ба энд $s_{i}$-аар $s$ тэмдэгт мөрийн $i$-дахь тэмдэгтийг $t_{i}$-аар $t$ тэмдэгт мөрийн $i$-дахь тэмдэгтийг тэмдэглэв.Жишээлбэл "$0011$" болон "$0110$" тэмдэгт мөрийн хоорондох Хамминг зай нь $|0 - 0| + |0 - 1| + |1 - 1| + |1 - 0| = 0 + 1 + 0 + 1 = 2$ болно.
Танд 2-тын тооллын системийн 2 ширхэг $a$ болон $b$ тэмдэгт мөр өгөгдөх ба $a$ тэмдэгт мөр болон $b$ тэмдэгт мөрийн бүх $|a|$ урт бүхий тасралтгүй дэд тэмдэгт мөрүүдийн хоорондох Хамминг зайнуудын нийлбэрийг олно уу.
Оролт
Эхний мөрөнд 2-тын тооллын системийн тэмдэгт мөр $a$ ($1 ≤ |a| ≤ 200 000$) өгөгдөнө.
2-дахь мөрөнд 2-тын тооллын системийн тэмдэгт мөр $b$ ($|a| ≤ |b| ≤ 200 000$) өгөгдөнө.
2 тэмдэгт мөр нь зөвхөн '$0$' болон '$1$'-ээс тогтсон байна.
Гаралт
$a$ тэмдэгт мөр болон $b$ тэмдэгт мөрийн бүх $|a|$ урт бүхий тасралтгүй дэд тэмдэгт мөрүүдийн хоорондох Хамминг зайнуудын нийлбэр болох ганц бүхэл тоог хэвлэнэ.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
01 00111
Гаралт
3
Оролт
0011 0110
Гаралт
2
Тэмдэглэл
Эхний хялбар жишээнд $|a|$ урт бүхий 4-н ширхэг $b$-ын тасралтгүй дэд тэмдэгт мөр байна:"$00$", "$01$", "$11$", болон "$11$"."$01$" болон "$00$"-ын Хамминг зай нь $|0 - 0| + |1 - 0| = 1$. "$01$" болон "$01$"-ын Хамминг зай нь $|0 - 0| + |1 - 1| = 0$. "$01$" болон "$11$"-ын Хамминг зай нь $|0 - 1| + |1 - 1| = 1$. "$11$" тэмдэгт мөр 2 ширхэг байгаа тул сүүлийн зай нь 2 удаа тооцогдоно.Иймд нийт нийлбэр нь $1 + 0 + 1 + 1 = 3$ болно.
2-дахь хялбар жишээ нь бодлогын өгүүлбэр дунд тайлбарлагдсан.