Заметим, что, если добавить в полупустой квадрат размера 2ⁿ × 2ⁿ печеньку максимального размера (она будет иметь размер 2(n - 1)), то наш квадрат разобьется на 4 квадрата величины 2^n - 1 × 2^n - 1, три из которых будут полупустыми квадратами, а один будет полностью заполнен. Отсюда следует формула f(n) = 3 * f(n - 1), f(0) = f(1) = 1. Переходя к замкнутой форме, получим ответ 3^n - 1 (при n > 0) и 1 (при n = 0).

Задача B.

Очевидно, что предложения следует помещать в SMS жадно. Действительно, если мы можем поместить предложение в текущее сообщение, то нету смысла начинать новое, т.к. при этом количество сообщений может увеличиться. Единственным подводным камнем в задаче была необходимость аккуратно обрабатывать пробелы между предложениями.

Задача C.

Для начала научимся решать более простую задачу: требуется подсчитать количество счастливых билетиков, в которых 1 ≤ a ≤ x и 1 ≤ b ≤ y. Преобразуем выражение a * b = rev(a) * rev(b) к выражению вида a / rev(a) = rev(b) / b. Переберем все возможные a и подсчитаем кол-во обычных несократимых дробей вида a / rev(a) (double, кстати, тоже работает =) ) с помощью какой-нибудь структуры, например, map из STL. Остается для каждого значения b найти количество совпадающих дробей a / rev(a) с rev(b) / b и добавить к ответу.

Теперь перейдем к нашей задаче.

Если счастливых билетов с ограничениями 1 ≤ a ≤ max_x и 1 ≤ b ≤ max_y меньше w, то x и y, удовлетворяющих условию задачи, не существует и следует вывести  - 1. 
Если решение существует, то воспользуемся методом двух указателей. 

Нам потребуется поддерживать количество счастливых билетов 1 ≤ a ≤ x и 1 ≤ b ≤ y. Для этого заведем две структуры типа map (назовем их m1 и m2). Научимся переходить из состояния (x,y) в состояния (x,y+1), (x+1,y), (x,y-1), (x-1,y). Если мы хотим увеличить (уменьшить) значение x, то к значению количества счастливых билетиков мы прибавим (отнимем) m2[x/rev(x)] и увеличим (уменьшим) значение m1[x/rev(x)] на единицу. В случае с изменением y следует выполнить аналогичные действия.

Зафиксируем некоторое состояние (x,y), где x = max_x, а y = 1 и подсчитаем для него количество счастливых билетиков. Будем увеличивать y, пока баланс счастливых билетиков не станет больше или равен w. Очевидно, что это будет такое наименьшее y для x, что в соответствующем диапазоне найдется достаточное количество счастливых билетов. Важно отметить, что в дальнейшем уменьшать y не будет иметь смысла. Прорелаксируем ответ и уменьшим x на единицу. Будем повторять действия, описанные в этом абзаце, пока x больше нуля. 

Так как x из ответа лежит в пределах от 1 до max_x и для кадого значения x из этого же диапазона мы нашли оптимальное значение y, то в результате работы алгоритма был просмотрен ответ с наименьшим значением x * y.

Так как каждый указатель не принимает одно значение дважды, и время, затрачиваемое на поддержку баланса, порядка логарифма, то общее время работы программы имеет асимптотику O(max_x * log(max_y) + max_y * log(max_x)).

Задача D.

Заметим что любая точка, лежащая внитри треугольника из первых трех точек, будет всегда содержаться внутри выпуклой оболочки в дальнейшем. Зафиксируем одну из таких точек и перенесем центр координат в нее. Будем хранить точки выпуклой оболочки в структуре типа map, где ключом будет угол для вектора из начала координат к какой-либо точке. Каждому углу будет соответствовать одна точка.

Научимся отвечать на запросы второго типа. Для точки в запросе (A) найдем ближайшую точку к ней по часовой (B) и ближайшую против часовой (C) стрелки. Если угол, образованный векторами AB и AC отрицательный, то точка лежит вне выпуклой оболочки, в противном случае точка лежит внутри или на границе. 

Теперь научимся обрабатывать запросы первого типа. Если точка из запроса (C) лежит внутри выпуклой оболочки, то ничего делать не надо. Найдем две ближайшие точки по часовой стрелке (ближнюю из них обозначим A, другую B). Если поворот от вектора AB к вектору AC положительный, то закончим обработку точек по часовой стрелке, иначе удалим из структуры точку A и повторим эти же действия. Подобным образом следует обработать точки, лежащие против часовой стрелки относительно C. 

Каждая точка добавляется максимум один раз и удаляется максимум один раз. Каждая из этих операций выполняется за O(log(h)), где h — количество точек в выпуклой оболочке. Итоговая асимптотика O(q * log(h)).

Задача E.

Заметим следующие факты. Пусть у нас есть зафиксированное состояние некоторого количества областных центров, тогда для каждой вершины не являющейся, областным центром следует выбрать ближайший к ней областной центр, т.к. d[i] <  = d[i + 1]. Утверждается что все вершины лежащие между некоторой вершиной x и ее центром g будут принадлежать этому центру g. Предположим что это не так, тогда g является не самым ближайшим центром для некоторой вершины между x и g, и для нее существует более ближайший центр u, но тогда должно быть dist[x][u] < dist[x][g], что приводит нас к противоречию. Таким образом получаем, что наше дерево должно быть разбито на некоторое количество поддеревьев и в каждом поддереве будет один областной центр. Для общности так же положим d[0] = 0.

Будем решать задачу используя "перекрестное" ДП.

Первая функция DP. D1(T, g, x, s) будет отвечать за формирование поддерева с областным центром g. T -- некоторое поддерево исходного дерева определяемое направленным ребром uv. областной центр g должен содержаться в T. Будем считать что городу v назначен областной центр g. Так я упомянул выше эта функция будет отвечать за формирование дерева с цетром g. Вся задача будет заключаться в выборе тех ребер которые будут ограничивать наше поддерево. Рисунок:

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

Пусть ребро xs является ограничивающим, тогда для поддерева T' (Вершины этого поддерева обведены в круг) вызовем функцию функцию ДП D2(T').

Вторая функция ДП будет перебирать каждую вершину в поддерве T' в качестве областного центра и вызывать D1.

В первой функции ДП имеется порядка O(n³) состояний т.к. поддеревьев T порядка O(n), вариантов выбора g столько же и пара (x;s) образует ребро, а ребер всего 2*n-2. Вторая функция ДП имеет O(v) состояний и переход выполняется за O(v). Таким образом решение требует O(n³) памяти и имеет асимптотику O(n³).