eolymp
bolt
Try our new interface for solving problems
Məsələlər

ABACABA сопоставление

ABACABA сопоставление

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Рассмотрим перестановку букв нижнего регистра английского алфавита: P = {p[1], p[2], ..., p[26]}. Используя P, можно сгенерировать следующую последовательность строк:

S[1] = p[1]

S[2] = S[1] + p[2] + S[1]

S[3] = S[2] + p[3] + S[2]

...

S[26] = S[25] + p[26] + S[25]

Легко обнаружить, что длина S[26] равна 2^26 - 1 буквам. Начало S[26] выглядит как p[1]p[2]p[1]p[3]p[1]p[2]p[1]....

Вам задана строка T из букв нижнего регистра английского алфавита. По фиксированной перестановке P Вы можете получить S[26], после чего заменить некоторые буквы T другими так, чтобы результирующая строка стала подстрокой S[26]. Вам следует минимизировать количество букв, которое следует заменить в T выбрав наиболее подходящую перестановку P.

Giriş verilənləri

Одна строка T (1 ≤ |T| ≤ 20000), содержащая буквы нижнего регистра английского алфавита.

Çıxış verilənləri

В первой строке вывести наименьшее количество букв, которое следует заменить. Во второй строке вывести позицию в строке S[26], где начинается результирующая подстрока (индексы нумеруются с 1).В третьей строке вывести перестановку P.

Nümunə

Giriş verilənləri #1
baca
Çıxış verilənləri #1
0
2
abcdefghijklmnopqrstuvwxyz
Giriş verilənləri #2
bcdbaaac
Çıxış verilənləri #2
3
2
cbdaefghijklmnopqrstuvwxyz
Mənbə 2013 Петрозаводск, Moscow SU ST + NNSU Contest, День 2, Август 24, Задача G