Подарок Диппера

Составим граф из всех букв и проведем ребра между разными буквами минимальной ценой замены. Посчитаем минимальное расстояние в графе изменений алгоритмом Флойда-Уоршелла за O(a3), где a — размер алфавита. Расстояние между вершиной a и b в графе соответствует минимальному количеству монет, которое нобходимо, чтоб получить из символа a символ b.

Рассмотрим делители n, только такие числа являются кандидатами на k-строку из n символов. Таких подходящих k будет порядка .

Будем решать для каждого k отдельно. Рассмотрим букву на позициях i, для каждого imodk посчитаем количество букв стоящих на таких позициях. Решаем независимо для каждого остатка от деления на k. Для этого переберем букву, которая будет стоять на этих позициях и посчитаем суммарную цену замены на необходимую букву.