0008. Филя

Input file name:	filya.in
Output file name:	filya.out
Time limit:	2 s
Memory limit:	64 megabytes

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

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

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

Формат входного файла

Во входном файле задана единственная строка, состоящая из заглавных латинских букв длиной от 1 до 255 символов. Символы строки определяют вид антиматерии в соответствующих контейнерах.

Формат выходного файла

В выходной файл необходимо вывести единственное число - ответ на поставленный вопрос.

Пример:

filya.in	filya.out
ABBCCA	3

Примечание

Филя должен выполнить следующие операции: ABBCCA → BBBCCA → CCCCCA → AAAAAA

Source: Командное школьное первенство Республики Карелия по программированию, май 2008.

Discuss       Submit a solution



Printable version