Codeforces Round 664 (Div. 1) |
---|
Закончено |
Boboniu определяет BN-строку как строку $$$s$$$ из символов 'B' и 'N'.
Он может совершать следующие операции над BN-строкой $$$s$$$:
Строка $$$a$$$ является подстрокой строки $$$b$$$ если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, нуля или всех) символов из начала и нескольких (возможно, нуля или всех) символов из конца.
Boboniu считает, что BN-строки $$$s$$$ и $$$t$$$ похожи если и только если:
Boboniu также определяет $$$\text{dist}(s,t)$$$, расстояние между $$$s$$$ и $$$t$$$, как минимальное число операций, необходимое чтобы сделать $$$s$$$ похожей на $$$t$$$.
Теперь Boboniu дал вам $$$n$$$ непустых BN-строк $$$s_1,s_2,\ldots, s_n$$$ и просит вас найти непустую BN-строку $$$t$$$, что максимальное расстояние до строки из $$$s$$$ минимизировано, т.е. вам нужно минимизировать $$$\max_{i=1}^n \text{dist}(s_i,t)$$$.
В первой строке записано одно целое число $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$).
Каждая из следующих $$$n$$$ строк содержит слову $$$s_i$$$ ($$$1\le |s_i| \le 5\cdot 10^5$$$). Гарантируется, что $$$s_i$$$ состоит только из 'B' и 'N'. Сумма $$$|s_i|$$$ не превосходит $$$5\cdot 10^5$$$.
В первой строке, выведите минимальное значение $$$\max_{i=1}^n \text{dist}(s_i,t)$$$.
Во второй строке, выведите подходящее $$$t$$$.
Если есть несколько возможных $$$t$$$, вы можете вывести любое.
3 B N BN
1 BN
10 N BBBBBB BNNNBBNBB NNNNBNBNNBNNNBBN NBNBN NNNNNN BNBNBNBBBBNNNNBBBBNNBBNBNBBNBBBBBBBB NNNNBN NBBBBBBBB NNNNNN
12 BBBBBBBBBBBBNNNNNNNNNNNN
8 NNN NNN BBNNBBBN NNNBNN B NNN NNNNBNN NNNNNNNNNNNNNNNBNNNNNNNBNB
12 BBBBNNNNNNNNNNNN
3 BNNNBNNNNBNBBNNNBBNNNNBBBBNNBBBBBBNBBBBBNBBBNNBBBNBNBBBN BBBNBBBBNNNNNBBNBBBNNNBB BBBBBBBBBBBBBBNBBBBBNBBBBBNBBBBNB
12 BBBBBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNNNNN
В первом примере $$$\text{dist(B,BN)}=\text{dist(N,BN)}=1$$$, $$$\text{dist(BN,BN)}=0$$$. Таким образом максимальное значение равно $$$1$$$.
Название |
---|