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

Уральская региональная командная олимпиада по программированию 2019

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

I. Викторина

Ограничение времени: 5.0 секунды
Ограничение памяти: 256 МБ
На телевидении всегда были популярны интеллектуальные шоу, в которых участники меряются своими умственными способностями, отвечая на сложные вопросы из различных областей. Вы решили создать свою викторину. Но самое сложное — не подготовить вопросы (их легко найти в Интернете), а сделать шоу красочным для зрителей. Поэтому гвоздь Вашей программы — огромный вращающийся барабан, разделённый на n секторов. В каждом секторе написана одна строчная буква латинского алфавита, обозначающая категорию вопроса. Барабан вращается только по часовой стрелке. Для удобства на одном из секторов нарисована стрелка, показывающая направление вращения.
Итак, вопросы составлены и разделены на категории, барабан готов, приглашения трём друзьям разосланы. И в самый последний момент Вам приходит мысль: буквы должны быть записаны на барабане не как попало, а в определённом порядке, чтобы было красивее! Подбежав к барабану, Вы начинаете его вращать, пытаясь найти хоть какой-нибудь узор.
Будем говорить, что барабан имеет период p (p > 0), если буква на каждом секторе совпадает с буквой на секторе, отстоящем на p позиций в направлении вращения. Барабан может иметь несколько периодов; в частности, барабан всегда имеет период n, так как секторов всего n. Вас интересует минимальный период. До начала шоу осталось всего ничего, и у Вас есть время поменять не более k букв, чтобы минимальный период был как можно меньше.
Определите наименьший возможный период, который может получиться у барабана после замены не более k букв.

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

В первой строке через пробел даны два целых числа n и k — количество секторов на барабане и наибольшее количество букв, которое можно заменить (1 ≤ n ≤ 105; 0 ≤ kn).
Во второй строке записано n строчных латинских букв — буквы, записанные на барабане, начиная с отмеченного стрелкой сектора в направлении вращения барабана.

Результат

В первой строке выведите одно число — наименьший положительный период, который может получиться у барабана.
Во второй строке выведите n строчных латинских букв — буквы, которые будут записаны на барабане после замены. Выводите буквы в том же порядке: начиная с отмеченного стрелкой сектора в направлении вращения. Использовать все k замен не обязательно.

Примеры

исходные данныерезультат
6 3
abcdef
3
abcabc
4 1
aaab
1
aaaa
4 0
aaab
4
aaab
Автор задачи: Валентин Зуев
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2146. Викторина