Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Слова - 2

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

Вася умеет быстро набирать на клавиатуре разные слова. Иногда он делает это так быстро, что в слове меняются местами какие-то две буквы (не обязательно стоящие подряд). И тогда, если Вася общается в чате, собеседник не всегда понимает его правильно: ведь, скажем, если Вася набрал «BEATS» и при этом, возможно, поменял местами две буквы, он мог иметь в виду и «BEATS», и «BEAST», и даже «BETAS». . .

Как хорошо бы было, если бы осмысленные слова нельзя было перепутать, даже если переставить в них какие-то две буквы! Васю заинтересовала теоретическая сторона этого вопроса. А именно: сколько же можно выделить слов из заданного набора букв так, чтобы никакие два слова, если в одном из них или даже в каждом переставить две буквы местами, не стали бы одинаковыми. Например, множество слов «BEAST» и «BETAS» не подходит, потому как из каждого слова можно перестановкой двух букв получить «BEATS». С другой стороны, «WORDS» и «SWORD» - подходящее множество: как ни переставляй пару букв в одном и в другом слове, одинаковую последовательность не получить.

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

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

В первой строке входного файла INPUT.TXT записаны подряд пять заглавных букв английского алфавита.

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

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

Пример

INPUT.TXTOUTPUT.TXT
1TATRATATRA
ARATT

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

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ