Короткі коментарі до задач
ХХ обласної олімпіади з інформатики

 Задача 1 (Word )

Для розв’язання задачі можна накопичувати слова в масиві та підраховувати їх частоту входження.

Задача 2 (CHESS)

Рекомендовано реалізувати дві "хвилі" від стартових клітин обох фігур і знайти клітину з однаковою оцінкою ходів. Якщо такої не існує, то вивести 0.

 Задача 3 (Подарунок для Мудрої Сови)

Задача реалізується перетворенням вихідної таблиці, починаючи з центральної клітинки в чотирьох різних напрямках за правилом A[i, j] = A[i, j] + Max(A[i-1,j],A[i, j+1]) для напрямку NE і т.д.

 Задача 4 (TAP_LAP)

Для розв’язання задачі досить було знайти для всіх нульових клітинок кількість сусідніх одиниць. Знайшовши таку суму, не забудьте помножити на висоту стіни L та довжину стіни D.

Задача 5 (GROUP)

В задачі необхідно знайти кількість компонент зв’язності неорієнтованого графа. Задача реалізується методом пошуку в глибину.

Задача 6 (GOLDTREE)

Кількість бруньок на гілках рівня X на день Y становить C(X,Y) – де C – біноміальний коефіцієнт.
C(X,Y) = X! / (Y! * (X-Y)!)
Результатом задачі є сума C(T,i) по всім і від K до N.

Задача 7 (AGENT)

Введемо операцію XOR для двох рядків. Результатом буде рядок, в якому операцію XOR застосовано до відповідних символів з кожного рядка S[i] = S1[i] XOR S2[i].
Таким чином, застосувавши операцію XOR для всіх рядків, в результаті отримаємо шуканий шифр. (Рядки, що були парну кількість разів, взаємно знищаться).

Задача 8 (MUSIC)

Задача розв’язується методом динамічного програмування.
Нехай F(N, K) – максимальна кількість пісень, які можна записати, якщо є перших N дисків, та перших K пісень.

Тоді отримуємо рекурентне співвідношення: F (N, K) = MAX(F(N-1, K-i) + G(K, i)) по всіх i від 1 до K.
G (K, i) – максимальна кількість пісень з послідовності (K-i, …, K), які можна вмістити на один компакт.
G (K, i) знаходиться наступним чином: рахується сума всіх чисел (довжин пісень) від K-i до K, і з цієї послідовності вилучаються максимальні елементи доти, доки сума не стане <= P (ємності одного диску).