|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Между сдачей ЕГЭ и поступлением в ВУЗ абитуриент Вася приехал к бабушке в деревню - отдохнуть от первого стресса и приготовиться ко второму. Добрая бабушка сразу предложила Васе замечательное средство для поправки расшатанных нервов: - А перекрась-ка мне, Васенька, забор! Вот, видишь - в нём N разноцветных досок. Надо перекрасить их так, чтобы никакие 2 соседние доски забора не были покрашены в одинаковый цвет. Вася очень хотел вернуться к приятной расслабленности и уговорил бабушку перекрасить только некоторые доски, но так, чтобы её условие соблюдалось. Всего у бабушки есть банки с K разными цветами. Так как когда-то давно забор красили из этих же банок, на заборе могут встречаться только имеющиеся цвета. Помогите Васе найти самый быстрый способ выполнить указание бабушки. Входные данные: В первой строке - два целых числа N и K (1≤N≤10000, 2≤K≤26). Вторая строка состоит из N букв латинского алфавита. Каждая буква обозначает отдельный цвет, “a”-первый цвет, “b”- второй и так далее. В строке используются только первые K букв латинского алфавита. Каждая буква обозначает цвет соответствующей доски в заборе. Выходные данные: Натуральное число - искомое число перекрашиваний. Для отправки решений необходимо выполнить вход. |