Masala F

Xotira 256 MB Vaqt 1000 ms
14

Change Binary strings

Sizga bir xil uzunlikdagi SS va TT satrlari beriladi. Ular faqat aa va bb dan tashkil topgan. Sizda SS satriga o'zgartirish kiritish uchun 2ta yo'l bor. 

  1. Istalgan xx sonini tanlaysiz (0x<S0\leq x < |S|) va agar SxS_x aa bo'lsa bb ga, bb bo'lsa esa aa ga o'zgartirasiz.
  2. Istalgan ikkita son, xx va yy sonlarini tanlaysiz (0x,y<S0\leq x, y < |S|) va SxS_x va SyS_y ni almashtirasiz.

Birinchi yo'l uchun sizdan 1 tanga, ikkinchi yo'l uchun esa yx|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.

  • 1N1061 \leq N \leq 10^6
  • S=T=N|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 bb ni aa harfiga o'zgartiramiz. +1 tanga. s = ‘aaa’;

s satrning birinchi harfi aa ni bb harfiga o'zgartiramiz. +1 tanga. s = ‘baa’;

s = t; #tangalar = 2;

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

 

Testlar misollardagidan farq qilishi mumkin!