Марсианский язык
(Время: 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.TXT | OUTPUT.TXT |
1 | 7 2 4 abacaba | 4 3 ab ac aba |
2 | 6 4 5 abacab | NO SOLUTION |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|