Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Марсианский язык

(Время: 1 сек. Память: 16 Мб Сложность: 45%)

Недавно ученые лаборатории радиоастрономии научно-исследовательского института формального исследования галактического антропогенеза (НИИ ФИГА) записали радиосигнал, передаваемый с Марса. После расшифровки выяснилось, что этим радиосигналом передавалась последовательность букв английского алфавита. Этот факт не вызвал у ученых большого удивления, больше их поразило то, что на Марсе есть радиопередатчики.

Для того, чтобы прочитать переданную информацию, необходимо последовательность букв разбить на слова. Известно, что слова в марсианском языке состоят не менее, чем из L и не более, чем из R букв.

Назовем качеством слова разность между максимальным и минимальным номером входящих в слово букв в алфавите. Например, качество слова ab равно 2-1 = 1, а слова abcz равно 26-1 = 25.

Пусть была передана строка s1, s2, ... , sN. Для того, чтобы разбить ее на слова, поставим между некоторыми соседними буквами пробелы. Тогда последовательности букв, ограниченные пробелами, началом и концом строки будут являться словами. Качеством разбиения строки на слова назовем сумма качеств всех входящих в него слов.

Ваша задача – найти для строки, полученной учеными лаборатории радиоастрономии, разбиение на слова марсианского языка, обладающее максимально возможным качеством.

Входные данные

Первая строка входного файла INPUT.TXT содержит три целых числа: N, L, R (1 ≤ L ≤ R ≤ N ≤ 5000). Вторая строка содержит N строчных букв английского алфавита.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите качество построенного разбиения. Во второй строке выведите число K – количество слов в разбиении. Далее выведите все слова разбиения по одному в каждой из последующих K строк. Конкатенация всех выведенных слов в том порядке, в котором они выведены должна быть равна исходной строке. Если возможных вариантов ответа несколько, выведите любой из них.

Если строку нельзя разбить на слова марсианского языка, то выведите в выходной файл строку NO SOLUTION.

Примеры

INPUT.TXTOUTPUT.TXT
17 2 4
abacaba
4
3
ab
ac
aba
26 4 5
abacab
NO SOLUTION

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 Четвертая личная олимпиада
 Пятая личная олимпиада
 Шестая личная олимпиада
 A. Число собранных яблок
 B. Перемешивание
 C. Марсианский язык
 D. Числа Фибоначчи - 5

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru