Masala A
Sehrgarning Kod Lentalari
Auron ismli sehrgar qadimiy qo‘lyozmalardan topilgan maxfiy kodlarni saqlaydi. Har bir kod qog‘oz lentaga yozilgan bo‘lib, unda kichik ingliz harflari ketma-ket joylashgan.
Sehrgar qo‘lida \(N\) ta kod lentasi bor.
U barcha lentalarni istalgan tartibda birlashtirib, bitta uzun kod hosil qilmoqchi. Har bir lentani ulashdan oldin uni:
- o‘z holicha qoldirish,
- yoki butunlay teskari aylantirish (
reverse)
mumkin.
So‘ng hosil bo‘lgan uzun kodning ikki uchi tutashtirilib, yopiq halqa hosil qilinadi.
Halqaning kuchi unda ketma-ket joylashgan bir xil harflarning eng uzun guruhi bilan aniqlanadi. Halqa yopiq bo‘lgani sababli, kodning oxirgi va birinchi harflari ham qo‘shni hisoblanadi.
Sehrgarga halqaning eng katta kuchini topishda yordam bering, ketma-ket keladigan bir xil harflarning maksimal mumkin bo‘lgan sonini aniqlang.
Kirish faylining dastlabki satrida bitta butun son, \(N(2 \le N)\) - lentalar soni kiritiladi.
Keyingi \(N\) ta satrning har birida bitta lentaning harflari ketma-ketligi.
| № | Chegaralar | Beriladigan ball |
| 1 | \(N \le 4\) \(S \le 20\) | 7 |
| 2 | \(N \le 50\) \(S \le 100\) | 14 |
| 3 | \(N \le 700\) \(S \le 1 \ 400\) | 19 |
| 4 | \(N \le 100\ 000\) \(S \le 200 \ 000\) | 30 |
| 5 | \(N \le 2 \ 000 \ 000\) \(S \le 4 \ 000 \ 000\) | 30 |
Bu yerda \(S\) barcha satr uzunliklari yig'indisini anglatadi.
Sehrgarga halqaning eng katta kuchini topishda yordam bering, ketma-ket keladigan bir xil harflarning maksimal mumkin bo‘lgan sonini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 ab cb |
2 |
| 2 |
3 abbc cbbb abb |
5 |
| 3 |
4 abbba aaaa aaa aa |
11 |
Telegram kanalimizga obuna bo'ling