Олимпиады для начинающих: Московская олимпиада, 8-9 класс, 2019 год

Рома и Денис отправились на соревнование по программированию. В долгой дороге ребята вспоминали операции над строками. Денис сказал, что в Python строки можно умножать на число, тогда Рома, программирующий на С++, решил придумать операцию перемножения строк. По версии Ромы, умножение строки \(s\) длины \(n\) на строку t обозначается как \(s \cdot t\) и равно строке \(t + s_1 + t + s_2 + \ldots + t + s_n + t\), где \(s_i\) обозначает \(i\)-й символ строки \(s\), а знаком « + » обозначено сложение (конкатенация) строк. Например, произведением строк « abc » и « de » является строка « deadebdecde », а произведением строк « z » и « ab » является строка « abzab ». Обратите внимание, что, в отличие от умножения чисел, произведение строк \(s\) и \(t\), вообще говоря, не равно произведению строк \(t\) и \(s\).

Денис решил продолжить мысль Ромы — он, как ценитель прекрасного, решил определить красоту строки как максимальную длину подряд идущей группы одинаковых букв. Например, красота строки « xayyaaabca » равна \(3\), так как самая длинная группа подряд идущих одинаковых букв — это « aaa », а красота строки « qwerqwer » равна \(1\), потому что все соседние буквы в ней различны.

Чтобы развлечь Дениса, Рома написал ему на листочке \(n\) строк \(p_1, p_2, p_3, \ldots, p_n\) и попросил его вычислить красоту строки \(( \ldots ((p_1 \cdot p_2) \cdot p_3) \cdot \ldots ) \cdot p_n\). Денис не до конца понял, как работает умножение Ромы, но не хочет признаваться в этом, поэтому просит посчитать красоту этой строки вас. Рома знает, что Денис слишком впечатлительный, поэтому гарантирует, что красота полученной строки не превосходит \(10^9\).