Вы, наверное, замечали, что многие компании используют для рекламы «красивые» номера телефонов, которые удобны для запоминания потенциальными клиентами. Но что делать, если номер вашей компании ничем не примечателен? Можно присмотреться к нему повнимательнее, а вдруг, если перегруппировать цифры номера некоторым образом, номер станет намного красивее? Например, если у вашей компании номер 872-73-33, то его можно сделать красивее, если перегруппировать цифры так: 8727-333.

Введем следующую оценку красоты разбиения номера. Будем разбивать номер дефисами на группы размером от 2 до 4 цифр. Теперь красотой разбиения назовем сумму баллов, которые приносит каждая группа. Эти баллы будем считать, пользуясь следующей таблицей.

	 
Шаблон группы          Баллы	 
aa                     2	 
aba                    2	 
aab, abb               2	 
aaa                    3	 
abac, baca             2	 
abab                   3	 
aabb                   3	 
abba                   4	 
baaa, abaa, aaba, aaab 3	 
aaaa                   5

В этой таблице символами «a», «b», «c» обозначены различные цифры. Например под шаблон «aab» подходят группы «223», «667», но не подходят «123» и «888».

Пользуясь предложенной оценкой, найдите наиболее красивое разбиение заданного номера.

В городском зоопарке содержатся животные n разных видов. Для участия в международной выставке «Три твари» зоопарк должен представить трех животных различных видов. Теперь служителей зоопарка интересует, сколькими способами можно выбрать трех животных для участия в выставке.

Например, если в зоопарке два медведя, тигр, лев и пингвин, то есть семь способов выбрать трех животных:

1) первый медведь, тигр и лев;

2) первый медведь, тигр и пингвин;

3) первый медведь, лев и пингвин;

4) второй медведь, тигр и лев;

5) второй медведь, тигр и пингвин;

6) второй медведь, лев и пингвин;

7) тигр, лев и пингвин.

Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

Дана текстовая строка. С ней можно выполнять следующие операции:

1. Заменить один символ строки на другой символ.

2. Удалить один произвольный символ.

3. Вставить произвольный символ в произвольное место строки.

Например, при помощи первой операции из строки "СОК" можно получить строку "СУК", при помощи второй операции - строку "ОК", при помощи третьей операции - строку "СТОК.

Минимальное количество таких операций, при помощи которых можно из одной строки получить другую, называется стоимостью редактирования или расстоянием Левенштейна.

Определите расстояние Левенштейна для двух данных строк.

Дана последовательность, требуется найти её наибольшую возрастающую подпоследовательность.