Олимпиадный тренинг

Задача . Тяжелая, вариант-1


Задача

Темы:

На уроке информатики учитель рассказал Васе про новый вид строк — минимально-символьные строки. Строка называется минимально-символьной, если символ, который встречается в ней минимальное количество раз, единственен. Например, строка "abacaba"минимально-символьная, потому что единственный символ, который встречается минимальное количество раз в ней — 'c'. В то же время строка "cababac" — не минимально-символьная, потому что символы 'b' и 'c' встречаются в ней минимальное количество раз, то есть не являются единственными.

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

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

В единственной строке входного файла input.txt записана строка s, характеризующая набор символов. Ее длина не превосходит 100.

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

В первой строке выходного файла output.txt требуется вывести минимальное количество минимально-символьных строк k, которое можно составить из данного набора символов, использовав каждый символ ровно один раз.

В следующих k строках выходного файла требуется вывести минимально-символьные строки, составленные из данного набора символов.

Если существует несколько правильных ответов, разрешается вывести любой из них.

Пример входных и выходных данных

 
Ввод Вывод
abacaba 1
abacaba
abcabc 2
abb
acc
abc 3
a
b
c
cababac 2
bcb
acaa

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python4
С++ Mingw-w649
Комментарий учителя