A: 379A - Новогодние свечки

Пусть cur_a количество целых свеч, cur_b — количество прогоревших. Изначально cur_a = a, cur_b = 0, тогда после того как прогорят все cur_a свечек, к ответу прибавится cur_a , а cur_b +  = cur_a, переделаем прогоревшие свечки в целые cur_a = cur_b / b , будем повторять это пока мы можем сделать хотя бы одну целую свечу. #### B: 379B - Новогодний подарок Если в кошелек необходимо положить более одной монетки, то между операциями "положить монетку" можно передвинуться к соседнему кошельку, затем обратно. Так как почти на каждую операцию "положить монетку" мы будем тратить не более 2 дополнительных операции, легко проверить, что количество инструкций на максимальный тест не будет превышать 300 * 300 * 3 = 270000, что меньше 10⁶.

C: 379C - Новогоднее изменение рейтинга

Можно отсортировать рейтинги в порядке неубывания, затем итерируясь по ним можно поддерживать текущий минимальный рейтинг cur, который не был ни кому отдан. Тогда если a_i > cur, i-му пользователю достанется a_i рейтинга и cur = a_i + 1, если a_i ≤ cur то i-му пользователю достанется cur рейтинга и cur увеличится на единицу.

D: 379D - Новогоднее письмо

При честном моделировании, получения итоговой строки, мы столкнемся с проблемой того, что она достаточно велика. Заметим что для каждой итерации нам достаточно хранить количество подстрок AC в текущей строке, а также первую и последнюю буквы. Таким образом мы научимся быстро моделировать алгоритм для произвольных начальных строк. Единственное что нам осталось перебрать начальные строки, для этого воспользуемся алфавитом из трех букв A, C и любой другой на ваш вкус. Переберем первую и последнюю буквы строки, а также количество подстрок AC, которые у нас могу получится с такими начальной и последней буквой. Перебрав таким образом s₁ и s₂ мы сможем посчитать количество подстрок AC в s_k.

E: 379E - Новогодние елочные украшения

Будем поддерживать объединение всех кусков до i-го, обозначим за S(i) площадь объединения первых i кусков. Тогда для того что бы узнать видимую площадь i-го куска нужно вычислить S(i) - S(i - 1), (S(0) = 0). Для простоты рассмотрим все отрезки с началом в x = 0 и концом в x = 1. Объединение будет представлять из себя выпуклую вниз ломанную, её можно представить как последовательность точек, каждая из которых соединена с соседней. Текущее объединение будет обновляться трапециями(часть куска). Понятно, что нам нужен будет только верхний отрезок, если он войдет в новое объединение тогда он должен будет пересечь два отрезка из объединения. Это пересечение мы можем найти за количество вершин в объединении, также каждый новый отрезок может добавить в объединение не более одной вершины. Если отрезок войдет в новое объединение то точки из объеденения, находящиеся под этим отрезком должны быть удалены. Таким образом количество вершин в объединении будет сравнимо с количеством кусков. Посчитав такие объединения для каждого сегмента, мы сможем получить ответ на задачу.

F: 379F - Новогоднее дерево

Скоро будет.

G: 379G - Новогодний кактус

На дереве эту задачу можно решать при помощи динамического программирования d[v][c][a], где v — номер вершины, c — тип этой вершины(чья игрушка висит или там не висит игрушек вовсе), a — количество игрушек в поддереве вершины v которые повесил Джек, само значение d[v][c][a] будет равно максимальному количеству игрушек, которые может повесить Джилл, при заданных условиях. Такую динамику можно считать перебирая сыновей вершины v и их тип и количество игрушек повешенных Джеком. Но у нас не дерево, а кактус, для того, что бы научиться решать эту задачу достаточно сжать циклы в кактусе в вершины тем самым получив обычное дерево, представив каждую вершину как последовательность вершин в цикле кактуса, из которых есть "продолжение" кактуса, и промежуточных вершин. Единственное что осталось, реализовать динамическое программирование на дереве, аккуратно обрабатывая каждую вершину.