Пары (25 баллов)

Автор задачи: Александр Ефимов

Первоисточник: тренировка в СамГУ, 2000

Задачу добавил: alef

Успешно сдано решений: 5

Входной файл содержит набор слов (словом считается последовательность символов, не содержащая символа перевода строки).
1-я буква может быть как заглавной так и строчной, остальные - строчные. Пусть некоторая последовательность букв встречается в обоих словах (регистр букв учитывается).

Процентом совпадения назовем максимальную длину такой последовательности, деленную на длину более короткого из этих слов,
умноженную на 100% и округленное до ближайшего целого. Требуется распределить слова по парам, так чтобы суммарный
процент совпадения для всех пар был наибольшим.

Формат входного файла:
N
слово₁
...
слово_N

где N - число слов от 2 до 12 (всегда четное).
Длина каждого слова не превышает 20 символов.

Формат выходного файла:
слово слово процент_совпадения
...
слово слово процент_совпадения

где:
в каждой паре слова стоят в алфавитном порядке.
пары отсортированы в алфавитном порядке по первым словам в них.

Пример входного файла:
4
Оля
Маша
Саша
Илья

Файл результата для данного примера:
Илья Оля 67
Маша Саша 75

Сдать задачу

Задать вопрос жюри по этой задаче