Разбор задач
1. Кодирование
Простая алгоритмическая задача. Алгоритм решения описан в условии задачи.
2. Палиндром
Задача на динамическое программирование. Сначала необходимо построить таблицу
T, в которой в ячейке
T[i,j] хранится минимальное количество добавляемых символов к строке
s[i…j] для получения палиндрома.
T[i,j] , если
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 баллов.