RoboContest

Xotira 256 MB Vaqt 1000 ms

14

Change Binary strings

Sizga bir xil uzunlikdagi $S$ va $T$ satrlari beriladi. Ular faqat $a$ va $b$ dan tashkil topgan. Sizda $S$ satriga o'zgartirish kiritish uchun 2ta yo'l bor.

Istalgan $x$ sonini tanlaysiz ( $0\leq x < |S|$ ) va agar $S_x$ $a$ bo'lsa $b$ ga, $b$ bo'lsa esa $a$ ga o'zgartirasiz.
Istalgan ikkita son, $x$ va $y$ sonlarini tanlaysiz ( $0\leq x, y < |S|$ ) va $S_x$ va $S_y$ ni almashtirasiz.

Birinchi yo'l uchun sizdan 1 tanga, ikkinchi yo'l uchun esa $|y-x|$ tanga olinadi. Siz esa S va T satrlarini tenglash uchun ketadigan minimal tangalar sonini toping!

Kiruvchi ma'lumotlar:

Birinchi qatorda N, S satrning uzunligi kiritiladi.

Keyingi qatorda S satri, 3-qatorda esa T satri beriladi.

$1 \leq N \leq 10^6$
$|S| = |T| = N$

Chiquvchi ma'lumotlar:

Yagona qatorda masala javobini chop eting!

Misollar

#	input.txt	output.txt
1	3 aab baa	2
2	4 abab aabb	1

Izoh:

1-testga izoh:

s = ‘aab’, t = ‘baa’;

s satrning oxirgi harfi $b$ ni $a$ harfiga o'zgartiramiz. +1 tanga. s = ‘aaa’;

s satrning birinchi harfi $a$ ni $b$ harfiga o'zgartiramiz. +1 tanga. s = ‘baa’;

s = t; #tangalar = 2;

Boshqa yo'li esa $x=0, y=2$ holatda $swap(s_x, ~ s_y)$ qilsak, s = t holatga keladi. #tangalar = 2;

Testlar misollardagidan farq qilishi mumkin!

RoboContest

Masala F

Change Binary strings