ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. 31 палиндром

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Ваша задача — для каждого префикса строки проверить, можно ли его разбить на 1, 2, 3, 4, 5, …, 31 непустой палиндром.

Исходные данные

На вход подаётся строка из n строчных латинских букв (1 ≤ n ≤ 300 000).

Результат

Выведите n целых неотрицательных чисел, разделяя их переводами строк. В i-й (1 ≤ in) строке требуется выдать число-маску, в которой (j − 1)-й бит равен единице, если префикс строки длины i можно разбить на j палиндромов.

Пример

исходные данныерезультат
abaa
1
2
5
14

Замечания

110 = 12; 210 = 102; 510 = 1012; 1410 = 11102; abaa = aba|a = a|b|aa = a|b|a|a.
Автор задачи: Михаил Рубинчик
Источник задачи: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2044. 31 палиндром