Новичок
-
Автор темы
- #1
Браслет
Ограничение по времени: 11 секунда
Варе подарили на День Рождения браслет, на котором по кругу записаны строчные буквы латинского алфавита. Изучив внимательно браслет, Варя поняла, что на нём указано какое‑то слово тарабарского языка, состоящее из NN букв. Особенность слов тарабарского языка в том, что в них всегда от одной до восьми букв «aa».
Подумав, Варя решила, что ей нужен не браслет, а цепочка, и захотела разрезать браслет ровно в одном месте, чтобы получившееся слово было палиндромом. Помогите Варе подсчитать количество способов разрезать браслет так, чтобы получилось слово‑палиндром. Определите позиции возможных разрезов —— номера букв, после которых можно разделить браслет (буквы в слове пронумерованы от 11 до NN).
Первая строка содержит целое число NN (1≤N≤2⋅106)(1≤N≤2·106) —— длину слова на тарабарском языке.
Вторая строка содержит последовательность из NN строчных букв латинского алфавита —— слово на тарабарском языке.
Формат выходных данных
В первой строке выведите целое число KK —— количество способов разрезать браслет.
В следующих KK строках выведите позиции возможных разрезов. Выводить позиции разрешено в любом порядке.
Система оценки
В этой задаче 2828 тестов, не считая тестов из условия. Каждый тест будет оцениваться независимо. Решения, правильно работающие при NN ≤≤ 20002000, будут оцениваться в 3636 баллов.
Пояснение
В первом тесте разрезать браслет можно двумя способами. Можно сделать разрез между буквами bb, тогда получится палиндром «baab»«baab», либо между буквами aa, тогда получится палиндром «abba»«abba».
В втором тесте нельзя разрезать браслет так, чтобы получился палиндром.
Ввод Вывод
4 2
abba 2
4
5 0
arbat
Ограничение по времени: 11 секунда
Варе подарили на День Рождения браслет, на котором по кругу записаны строчные буквы латинского алфавита. Изучив внимательно браслет, Варя поняла, что на нём указано какое‑то слово тарабарского языка, состоящее из NN букв. Особенность слов тарабарского языка в том, что в них всегда от одной до восьми букв «aa».
Подумав, Варя решила, что ей нужен не браслет, а цепочка, и захотела разрезать браслет ровно в одном месте, чтобы получившееся слово было палиндромом. Помогите Варе подсчитать количество способов разрезать браслет так, чтобы получилось слово‑палиндром. Определите позиции возможных разрезов —— номера букв, после которых можно разделить браслет (буквы в слове пронумерованы от 11 до NN).
Браслет из первого теста
Для справки: палиндром —— слово, одинаково читающееся в обоих направлениях, например, «abba»«abba».Формат входных данныхПервая строка содержит целое число NN (1≤N≤2⋅106)(1≤N≤2·106) —— длину слова на тарабарском языке.
Вторая строка содержит последовательность из NN строчных букв латинского алфавита —— слово на тарабарском языке.
Формат выходных данных
В первой строке выведите целое число KK —— количество способов разрезать браслет.
В следующих KK строках выведите позиции возможных разрезов. Выводить позиции разрешено в любом порядке.
Система оценки
В этой задаче 2828 тестов, не считая тестов из условия. Каждый тест будет оцениваться независимо. Решения, правильно работающие при NN ≤≤ 20002000, будут оцениваться в 3636 баллов.
Пояснение
В первом тесте разрезать браслет можно двумя способами. Можно сделать разрез между буквами bb, тогда получится палиндром «baab»«baab», либо между буквами aa, тогда получится палиндром «abba»«abba».
В втором тесте нельзя разрезать браслет так, чтобы получился палиндром.
Ввод Вывод
4 2
abba 2
4
5 0
arbat
