Загрузка [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Подразделы

Другие разделы

Дата и время

29/07/2025 08:50:37

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printРазбор задач

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

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

print2. Палиндром

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

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

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

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

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