Для удобства обозначим размеры монстра через x₁, x₂, x₃.

1. Решение за O(min(k, x₁ + x₂ + x₃))

Всего можно провести не более (x₁ – 1) + (x₂ – 1) + (x₃ – 1) разрезов, поэтому можно считать, что k <= x₁ + x₂ + x₃ – 3. Для каждой из трёх координат будем хранить число a_i – количество уже проведенных разрезов вдоль соответствующей координаты. Проделаем k раз следующую операцию: рассмотрим те числа a_i, которые мы можем увеличивать (то есть вдоль соответствующей координаты еще не проведены все возможные разрезы, назовем такие координаты «неполными»). Среди полученных a_i выберем наименьшее число a_j и проведем разрез вдоль соответствующей координаты (в результате число a_j увеличится на 1). Теперь рассмотрим получившееся после k операций множество {a₁, a₂, a₃}. Заметим, что при таком алгоритме наибольшее число этого множества будет принимать наименьшее возможное значение, а наименьшее число – наибольшее возможное значение. Это, в свою очередь, гарантирует максимальность произведения (a₁ + 1) * (a₂ + 1) * (a₃ + 1) при фиксированной сумме a₁ + a₂ + a₃ = k.

2. Решение за O(1)

Вместо того чтобы моделировать все k операций, можно быстро определить, чему будут равны числа a_i после применения алгоритма, описанного в пункте 1.

Пусть x – наименьшее среди чисел x_i - 1. Если x * 3 >= k, то на каждой итерации алгоритма множество «неполных» координат будет содержать все 3 координаты. Значит, за первые (k / 3) * 3 шага, каждое из чисел a_i мы увеличим на (k / 3). Далее, в зависимости от остатка k при делении на 3, от 0 до 2 чисел a_i будут увеличены на 1. Таким образом, числа a_i найдены.

В противном случае (x * 3 < k) за первые x * 3 шага каждое из чисел a_i мы увеличим на x. После этого у нас останется не более двух «неполных» координат, обработать которые можно аналогичным образом, выбрав наименьшее значение x среди них.

Задача B.

Можно считать, что у нас всегда ровно n призовых мест, но за некоторые из них дается 0 очков.

Отсортируем все места по количеству призовых очков (b_i), а участников - по количеству уже набранных очков (a_i). Определим, в каком случае Вася сможет занять наилучшее место. Понятно, что в лучшем случае сам Вася получит b₀ очков (где b₀ – наибольшее среди чисел b_i). Будем считать, что теперь у него стало в сумме v очков. Теперь нам надо раздать остальные призовые очки участникам так, чтобы количество участников, обогнавших Васю, было наименьшим. Для этого определим, какое наибольшее число призов мы сможем вручить так, чтобы получившие их участники не обогнали Васю. Заметим, что если мы смогли вручить таким образом k призов, то мы так же сможем вручить и k наименьших (с точки зрения количества призовых очков) призов. Далее очевидно верно следующее утверждение: если приз в t очков мы можем вручить как участнику i, так и участнику j, причем a_i > a_j, то выгоднее вручить этот приз участнику i, более формально: если существует способ раздать k призов, при котором данный приз достался участнику j, то существует и способ раздать k призов, при котором данный приз достался участнику i. Строго доказать это можно следующим образом. Рассмотрим способ вручить k призов, при котором участник j получил приз в t очков, а участник i – s очков или не получил приза вовсе. В первом случае можно поменять призы участников i и j. Действительно, поскольку a_i > a_j, и a_i + s < v (поскольку участник i получил приз), то a_j + s < v, а a_i + t < v по предположению. Во втором случае можно приз t просто отдать участнику i, а участника j оставить без приза. В обоих случаях мы получили допустимый вариант вручения k призов, при котором участник i получил приз t.

Теперь, пользуясь полученными утверждениями, можно раздавать призы жадно следующим образом. Будем раздавать призы, начиная с наименьшего приза. При этом будем просматривать участников, начиная с наилучшего (разумеется, Васю и наилучший приз мы не рассматриваем). Для каждого приза i будем двигаться по списку участников (j), пока не получим b_i + a_j < v. Если такого участника не нашлось, то мы больше не сможем выдать приз так, чтобы получивший его участник не обогнал Васю. В этом случае алгоритм останавливается и ответом будет n – k, где k – количество уже врученных призов. Если такой участник j нашелся, то мы можем ему вручить приз b_i и перейти к следующему призу. Итого, сложность этого шага есть O(n).

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

Общая сложность алгоритма есть O(n * log(n)) за счет необходимости сортировки.

Задача C.

Заметим, что если мы поставили в позицию p строки s некоторый символ c, то он не влияет на благозвучие, получаемое за счет символов в позициях (p+2) и больше. Таким образом, мы получаем стандартную задачу динамического программирования. Состояние описывается тремя параметрами: p – количество уже просмотренных букв строки (или номер символа строки, который мы на данный момент рассматриваем), c – предыдущий символ строки, t – количество разрешенных изменений символов. Пересчет состояния осуществляется перебором буквы, которую мы будем ставить на место p, при этом надо учитывать, что мы можем изменять букву только в случае, когда t > 0. Итого, получаем формулу пересчета:

d[n][*][*] = 0

d[p][c][t] = d[p + 1][s[p]][t] + bonus[c][s[p]] при t = 0

d[p][c][t] = max(d[p + 1][c’][t – (c’ <> s[p])] + bonus[c][c’])

где n - длина строки s.

Сложность алгоритма - O(n * k * h^2), где h - размер алфавита (в данной задаче h = 26).