A. Для решения задачи можно было вывести одни из следующих формул:
res = abc - (a - 1)(b - 1)(c - 1), res = ab + bc + ca - a - b - c + 1, или какую любо аналогичную.
Кроме того, задачу можно было решить за O(a + b + c) — аккуратно спускаться от верхнего слоя к нижнему и суммировать общее число плиток.

Автор — Ripatti .

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

Нетрудно понять, что граф состоит из цепочек, циклов и отдельных вершин. Каждую из этих компонент можно легко покрасить нужным образом в 2 цвета, кроме одного случая: циклы нечетной длины. Таким образом, для решения задачи необходимо выкинуть по 1 вершине из каждого нечетного цикла. После данной операции у нас может остаться нечетное число вершин — тогда выкинем еще одну. В итоге получим граф из четного числа вершин, состоящий из цепочек, четных циклов и отдельных вершин. Такой граф легко раскрасить нужным способом.

Авторы — Gerald , Ripatti .

С. Первое решение: разбор случаев.
1. k = 1. Здесь для n ≤ m + 1 нужно 3 сотрудника, а для n > m + 1 — 2 сотрудника, кроме одного хитрого случая: для n = 2, m = 2, k = 1 ответ 4.
2. k > 1. Для n = m ответ 2k + 1, для всех остальных случаев ответ 2k.
Во всех случаях легко построить сами решения, а так же вручную доказать их корректность.

Второе решение: жадность.
Заведем массив достаточно большого размера, в котором будем хранить текущее число работников в каждый из первых несколько дней. Теперь просто будем идти по нему слева направо от 1го для до n + m-го и нанимать работников так, чтобы все было хорошо. А именно: нанимаем работника если в текущий день персонала меньше k или же если в следующий день персонала 0 человек (этот работник нужен чтобы передать ключ).
Можно показать, что это решение работает за O((n + m)k).
Это решение так же работает и для случаев n < m, но за более большую асимптитику.

Авторы — Gerald , Ripatti .

D. Для каждого сектора отсортируем все перемычки по расстоянию от центра паутины. Теперь для каждого сектора при помощи трех указателей (один для данного сектора, 2 для соседних) посчитаем число плохих ячеек. Собственно, все. Главное не запутаться.

Решение за , где m — общее число перемычек.

Автор — Ripatti .

E. Цифровой корень почти всегда равен самому числу по модулю k - 1. Единственное расхождение для цифровых корней 0 и k - 1 — для них обоих число по модулю k - 1 будет 0. Но цифровой корень 0 мы можем получить только из числа вида 00...00, количество которых можно посчитать отдельно. Отсюда легко понять как вычислить количество подстрок с нужным цифровым корнем, зная число подстрок, равных по модулю некоторому числу.

Теперь давайте поймем как получить число подстрок нужного модуля. Будем идти по строке слева направо и поддерживать для каждого модуля количество префиксов с таким модулем в массиве dp[] размера k. Пусть текущая позиция i. Тогда число подстрок с модулем b, оканчивающихся в позиции i, равно числу префиксов левее позиции i с модулем (x - b)mod(k - 1), где x — модуль подстроки s[1... i]. Т.е. просто dp[(x - b)mod(k - 1)].

Чтобы это решение прошло по времени, массив dp[] следует заменить на какой нибудь ассоциативный массив. Например, на std::map в языке С++ или на хэштаблицу.

Итого решение за O(nz), где z — сложность доступа к массиву ( для std::map или O(1) для хэштаблицы).

Автор — Ripatti.