Разбор задач

1. Кодирование

Простая алгоритмическая задача. Алгоритм решения описан в условии задачи.

2. Палиндром

Задача на динамическое программирование. Сначала необходимо построить таблицу `T`, в которой в ячейке `T[i,j]` хранится минимальное количество добавляемых символов к строке `s[i…j]` для получения палиндрома. `T[i,j]\ =\ T[i+1,j-1]`, если `s[i]=s[j]`, `T[i,j]\ =\ min(T[i,j-1],T[i+1,j])\ +\ 1` если `s[i]≠s[j]`. Выполняя обратную трассировку по таблице `T` легко найти палиндром-результат. "Жадное" частичное решение, выполняющее анализ строки одновременно слева и справа и добавляющее в результат меньший из концов в случае несовпадения, дает 15 баллов.

3. Преобразования

Задача заключается в выводе рекуррентного соотношения. Рассмотрим двух соседей 00, на следующем шаге эти соседи исчезнут 1010, а еще через шаг пара 00 появится снова 01100110. Кроме того каждая 1 через два шага порождает соседей 00. Количество 1 на каждом шаге удваивается. Окончательно формула выглядит так `S_0=0`, `S_1=0`, `S_k\ =S_{k-2}\ +\ 2^{k\ -\ 2}`. Для вычислений потребуется длинная арифметика (только операция сложения и печать) Частичное решение – выполнение указанных преобразований с помощью строк – дает 18 баллов. Правильная формула с использованием extended вместо длинной арифметики – 24 балла.

4. Декомпозиция

Жадным способом выделяем максимально длинные ожерелья из последовательности слева направо. Так как выявляются ожерелья максимальной длины, то выполняется условие `T_i\ T_{i+1}` не является "ожерельем". Второе условие вытекает из первого – если бы выполнялось `T_{i+1}\ ≥\ T_i` , то `T_i\ T_{i+1}` являлось бы ожерельем. Проверка произвольной последовательности на то, что она является ожерельем выполняется путем сравнения этой последовательности со всеми ее циклическими сдвигами. Частичное решение – разбиение последовательности на подпоследовательности вида (0…01…1) – дает 15 баллов.