A. Секретный код

Задача относится к типу «сделайте что просят». Очевидно, как посчитать количество совпадающих символов у двух строк. Для проверки встречался ли данный символ в исходной строке достаточно предподсчитать массив логических значений used[c], где хранится true если символ c встречался в секретном коде и false иначе.

B. Хаос

Рассмотрим наибольшее среднее арифметическое двух чисел, которое можно получить используя два числа из входных данных. Легко заметить, что это среднее арифметическое двух наибольших чисел массива.

Ответ больше этого числа никак не получить, так как при замене двух чисел на две копии их среднего арифметического среднее арифметическое двух максимумов не увеличивается.

Теперь рассмотрим стратегию, как можно добится этого результата: На каждом ходу берем эти два максимума и любое число, стираем, затем дважды пишем среднее арифметическое максимумов. Начиная со второго хода два максимума перестанут меняться и будут равны ответу.

C. Новое приключение Марти и Дока

Требуется минимизировать сумму Sum(i = 1..n, j = 1..m, 2·a_i, j·(|i - x| + |j - y| + 1)). Заметим, что нет слагаемых, зависящих от обеих коорданат, поэтому ее можно разбить на три: Sum(2·a_i, j), Sum(2·a_i, j·|i - x|) и Sum(2·a_i, j·|j - y|).

Первая сумма — константа, вторую и третью можно минимизировать независимо, выбирая, соответственно, ряд и столбец. Исходя из вида второй суммы получаем, что оптимальный ряд — медиана набора чисел Sum(j = 1..m, a_1, j) раз 1, Sum(j = 1..m, a_2, j) раз 2, ..., Sum(j = 1..m, a_n, j) раз n.

Аналогично для второй координаты.

D. Разбиение на команды

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

Для начала отсортируем все числа и посчитаем, сколько раз каждое число встречается в массиве. Если в команде есть школьники с навыками l и r, то все школьники с силой m, где l < m < r, тоже обязательно будут в этой команде. Таким образом, можно решать задачу, считая значения dp[i][j][f] — количество способов разбить всех школьников с навыком не большим i на j команд, если в последнюю (одну из команд, в которой есть школьник силы i) команду мы f=true|false добавим или не добавим еще учеников. Переход — пусть у нас есть k школьников с силой i + 1. Тогда переберем g — на сколько команд мы их разобьем, и, используя вспомогательное значение f[k][g] обновим значения dp[i + 1][j'][f']. Заметим, что время заполнения массива есть O(nk), поскольку общее число значений g для фиксированного j равно n.

Чтобы посчитать f[k][g] — количество способов разбить k школьников одинаковой силы на g команд, нужно посмотреть, в какой команде находится k-й школьник — либо в своей отдельной команде (f[k - 1][g - 1]), либо в одной из уже существовавших до него (f[k - 1][g]·g).

Итого, каждый из массивов f и dp заполняется за O(nk), поэтому все решение работает за O(nk).

E. Максимальная сумма

Отсортируем b_j по убыванию. Будем добавлять в массив a_i все числа, не меньше очередного b_j. Таким образом в массиве a_i будут содержаться только отрезки чисел, для которых выполнено a_i ≥ b_j. При добавлении очередного a_i, на каждом вновь образованном отрезке нужно находить отрезок с максимальной суммой. Это является достаточно стандартной подзадачей, которую можно решить, например, деревом отрезков (см, например, обсуждение здесь http://codeforces.net/blog/entry/17780).