Masala #R111C
Ota Smurfning afsuni
Ota Smurf qishloqni himoya qiluvchi afsun tayyorlamoqchi. Afsun faqat uning matni palindrom bo'lsa ishlaydi.
Afsun matni uzunligi \(n\) bo'lgan \(s\) satridan iborat. Har bir \(i\) uchun, \(s_i\) belgisini boshqa kichik lotin harfiga almashtirish narxi \(c_i\) ta smurf mevaga teng.
Ota Smurfga afsun matnini palindrom qilish uchun kerak bo'ladigan minimal smurf mevalar sonini topishga yordam bering.
Kiruvchi ma'lumotlar:
Birinchi qatorda \(t\) — testlar soni beriladi.
Har bir test quyidagi ko'rinishda beriladi:
Birinchi qatorda \(n\) — afsun matni uzunligi beriladi.
Ikkinchi qatorda uzunligi \(n\) bo'lgan \(s\) satri beriladi.
Uchinchi qatorda \(n\) ta butun son \(c_1,c_2,\ldots,c_n\) beriladi.
Cheklovlar:
\[
1 \le t \le 10^4
\]
\[
1 \le \sum n \le 2 \cdot 10^5
\]
\[
1 \le c_i \le 10^9
\]
\(s\) faqat kichik lotin harflaridan iborat.
Chiquvchi ma'lumotlar:
Har bir test uchun alohida qatorda afsun matnini palindrom qilish uchun kerak bo'ladigan minimal smurf mevalar sonini chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 5 abaca 3 10 5 2 7 4 abcd 8 1 4 9 6 abccba 1 2 3 4 5 6 |
2 9 0 |
Izoh:
Birinchi testda faqat \(s_2\) va \(s_4\) belgilar farq qiladi. Ulardan arzonrog'ini almashtirish uchun \(2\) ta smurf meva kerak.
Ikkinchi testda \(s_1\) va \(s_4\), shuningdek \(s_2\) va \(s_3\) juftliklari farq qiladi. Minimal xarajat \(8+1=9\).
Uchinchi testda satr allaqachon palindrom.
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring,
agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin
Telegram kanalimizga obuna bo'ling