Masala #1D4D45FRDX
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!
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\)
Yagona qatorda masala javobini chop eting!
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 aab baa |
2 |
| 2 |
4 abab aabb |
1 |
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!
Telegram kanalimizga obuna bo'ling