Codeforces Global Round 25 |
---|
Закончено |
Вам дана строка $$$s$$$, состоящая из строчных латинских букв. Вам нужно разбить$$$^\dagger$$$ эту строку на некоторое количество подстрок так, чтобы каждая подстрока не была палиндромом$$$^\ddagger$$$.
$$$^\dagger$$$ Разбиение строки $$$s$$$ — это упорядоченная последовательность некоторых $$$k$$$ строк $$$t_1, t_2, \ldots, t_k$$$, таких, что $$$t_1 + t_2 + \ldots + t_k = s$$$, где $$$+$$$ обозначает операцию конкатенации.
$$$^\ddagger$$$ Строка $$$s$$$ называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, $$$\mathtt{racecar}$$$, $$$\mathtt{abccba}$$$ и $$$\mathtt{a}$$$ являются палиндромами, а $$$\mathtt{ab}$$$, $$$\mathtt{dokibird}$$$ и $$$\mathtt{kurosanji}$$$ — нет.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Каждый набор входных данных содержит строку $$$s$$$, состоящую из строчных латинских букв ($$$1 \le |s| \le 10^6$$$).
Гарантируется, что сумма $$$|s|$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите в отдельной строке «YES», если существует разбиение $$$s$$$, части которого не являются палиндромами, или «NO», если такого разбиения не существует.
Если ответ «YES», то во второй строке выведите целое число $$$k$$$ — количество частей, на которое нужно разбить $$$s$$$, чтобы каждая часть не была палиндромом. В третьей строке выведите $$$k$$$ строк $$$t_1, t_2, \ldots, t_k$$$, представляющих такое разбиение. Если таких разбиений несколько, выведите любое из них.
3sinktheyachtllllllllluwuowouwu
YES 1 sinktheyacht NO YES 3 uw uow ouwu
В первом наборе входных данных, поскольку $$$\mathtt{sinktheyacht}$$$ уже не является палиндромом, разбиение $$$[\mathtt{sinktheyacht}]$$$ является допустимым.
Во втором наборе входных данных, поскольку любая подстрока строки $$$s$$$ является палиндромом, не существует допустимых разбиений.
В третьем наборе входных данных еще одно допустимое разбиение — $$$[\mathtt{uw},\mathtt{uo}, \mathtt{wou}, \mathtt{wu}]$$$.
Название |
---|