A. Нужно было три раза подсчитать количество гласных букв в трех строках. Затем сравнить то, что получилось, с числами 5, 7 и 5. Если все совпало - вывести YES, иначе вывести NO.

Автор задачи - Ripatti.


B. Сначала можно было [n / 7] раз вывести строку ROYGBIV ([] - это округление вниз). А затем в зависимости от остатка при делении n на 7, вывести одну из следующих строк: "", "G", "GB", "YGB", "YGBI", "OYGBI", "OYGBIV". Полученная строка будет удовлетворять условию задачи.

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

Автор задачи - Ripatti.


C. Если n четно, то всегда выигрывает Марсель - он просто симметрично повторяет ходы Тимура.

Теперь рассмотрим случай, когда n нечетно. Если Тимур не может сделать хода - он проигрывает автоматически. Если же он может сделать ход, то он всегда может разгрызть одно из бревен так, чтобы далее его части нельзя было разгрызть на меньшие части. Чтобы это сделать, нужно найти наименьшее число t такое, что k ≤ t < m и t|m, и разгрызть бревно на части длины t. После этого Тимур симметрично повторяет ходы Марселя и выигрывает.

Чтобы проверить может ли Тимур сделать ход, нужно перебрать все делители m. Если хоть для одного из них (предположим, t), выполняется k ≤ t < m, то ход сделать возможно. Проверку всех делителей можно сделать за время .

Автор задачи - Lepetrandr.


D. Подобно классической задаче с подсчетом количества квадратиков в круге, данная задача решается аккуратный обходом ячеек по окружности. Сначала от центра круга будем подниматься вверх и найдем самый верхний шестиугольник, который помещается в круг. Затем сместимся на один шестиугольник вправо и вверх и от него будем двигаться вниз, пока не найдем шестиугольник, лежащий в круге. Так будем повторять до тех пор, пока не дойдем до правого края круга.

В процессе выполнения вышеописанного алгоритма к ответу будем прибавлять высоты столбиков шестиугольников. Нетрудно понять, что мы в итоге затратим O(n) времени.

О реализации. Все интересующие нас точки имеют координаты вида . Поэтому расстояние до центра координат можно (и нужно) считать в целых числах. Например, проверка на то, что точка лежит внутри круга радиуса R имеет вид x² + 3y² ≤ 4R².

Эту задачу также можно было решить за . Просто для каждого столбика шестиугольников двоичным поиском найдем сколько шестиугольников в нем помещается в круг.

Автор задачи - Ripatti.


E. Сначала посчитаем несложную динамику от 5 параметров dp[t][x0][y0][x][y]. В каждой ячейке данной динамики будет стоять true если в момент t какой-нибудь ученый из начального блока (x0 y0) может добраться в блок (x y). В процессе пересчета данной динамики нужно учитывать распространение охлаждающей жидкости.

Теперь построим граф, состоящий из 4 частей: исток (1 вершина), первая доля (n × n вершин), вторая дола (тоже n × n вершин) и сток (1 вершина). Каждой вершине каждой доли соответствует один из блоков. От истока к первой доле проведем ребра с пропускными способностями, равными количеству ученых в соответствующих блоках. От второй доли к стоку проведем ребра с пропускными способностями, равными количеству спасательных капсул в соответствующих блоках. Из первой доли во вторую проведем ребра бесконечной пропускной способности если согласно dp ученый за время до взрыва из соответствующего блока первой доли может добраться до соответствующего блока второй доли.

Теперь в полученном графе найдем максимальный поток - он и будет ответом на задачу.

Решение имеет сложность O(tn⁴ + kn⁶), где k - максимальное количество ученых в одной клетке (в данной задаче оно равно 9).

Автор задачи - Ripatti.