Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Ксениа ба Хэминг
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Ксениа нь мэргэжлийн бус программист. Өнөөдөр түүний мэдээллийн технологийн хичээл дээр "Хэмингийн зай" гэж юу болохыг сурсан.
$n$ урттай $s=s_1s_2...s_n$ ба $t=t_1t_2... t_n$ тэмдэгт мөрүүдийн хоорондын Хэмингийн зай гэдэг нь $\sum_{i=1}^n [s_i \not=t_i]$ юм. Энд $[s_i\not=t_i]$ нь Айверсоны тэмдэглэгээ ба энэ нь $s_i\not=t_i$ үед нэгтэй тэнцэх, эсрэг тохиолдолд тэгтэй тэнцэнэ.
Ксениа урт $a,b$ тэмдэгт мөрүүдийн хоорондын Хэмингийн зайг олохыг хүсчээ . Эхний тэмдэгт мөр $a$ нь $x$ тэмдэгт мөрийг $n$ удаа залгаж бичихэд үүсэх бол 2 дахь тэмдэгт мөр $b$ нь $y$ тэмдэгт мөрийг $m$ удаа залгаж бичихэд үүснэ. $n,x,m,y$ тоонууд өгөгдсөн бол Ксениад 2 тэмдэгт мөрийн хоорондын Хэмингийн зайг олоход тусална уу.
Оролт
Эхний мөрөнд $n, m (1\le n,m\le 10^{12})$ тоонууд өгөгдөнө. 2 дахь мөрөнд хоосон биш $x$ тэмдэгт мөр өгөгдөнө. 3 дахь мөрөнд хоосон биш $y$ тэмдэгт мөр өгөгдөнө. Аль аль нь ихдээ $10^6$ ширхэг Англи цагаан толгойн жижиг үсгээс тогтоно.
$a,b$ тэмдэгт мөрүүд нь адил урттай байхаара өгөгдөнө.
Гаралт
2 тэмдэгт мөрийн хоорондын Хэмингийн зайг олж хэвлэнэ үү.
Жич: С++ хэл хэрэглэж байгаа бол 64-бит бүхэл тоог уншихдаа %lld тодорхойлогчийг ашиглахгүй байхыг зөвлөж байна. cin, cout стриймүүд эсвэл %I64d тодорхойлогчийг ашиглана уу.
Орчуулсан: Төрбат
Жишээ тэстүүд
Оролт
100 10 a aaaaaaaaaa
Гаралт
0
Оролт
1 1 abacaba abzczzz
Гаралт
4
Оролт
2 3 rzr az
Гаралт
5
Тэмдэглэл
In the first test case string $a$ is the same as string $b$ and equals 100 letters a$. As both strings are equal, the Hamming distance between them is zero.
In the second test case strings $a$ and $b$ differ in their 3-rd, 5-th, 6-th and 7-th characters. Thus, the Hamming distance equals 4.
In the third test case string $a$ is rzrrzr$ and string $b$ is azazaz$. The strings differ in all characters apart for the second one, the Hamming distance between them equals 5.