A. Башни
Общее количество башен равно количество различных чисел в данном наборе. Чтобы получить высоту наибольшей башни, можно было подсчитать для каждой длины количество брусков с такой длинной, и из этих чисел выбрать максимальное.
B. Компьютерная игра
Ограничения в задаче позволяли решать её следующим образом: будем хранить текущее количество здоровья у босса, и суммарный наносимый урон по нему. На очередном шаге выберем из еще не использованных свитков такой, который можно использовать на текущей секунде. Из всех таких, найдем свиток, который наносит больше всего урона, и применим его. Если в какой-то момент мы не смогли использовать ни один из свитков, и суммарный урон не превышает регенерацию, то выводим, что ответа не существует. Иначе продолжаем итерировать алгоритм, пока количество жизни босса не станет неотрицательным.
C. Древнеберляндский язык
Одно из самых простых для понимания решений в данной задаче выглядит так: отсортируем строки по возрастанию длины, при этом запомнив их номер в исходном списке. Будем последовательно строить наш набор, начиная с самых коротких строк: строками длины один могут быть только строки “0” и “1”. Если количество строк длины один в наборе больше двух, следовательно, ответа не существует. Добавим нужное количество строк длины один в ответ на свои места (для этого мы запомнили их номера), и удалим из текущего списка. Затем посмотрим на строки длины два: каждую из оставшихся строк длины 1 можно продолжить двумя способами (дописав к каждому из них символы 0 и 1). Добавим нужное количество строк длины два в наш набор, и снова увеличим длину оставшихся строк на единицу. Будем продолжать этот процесс до тех пор, пока не составим набор целиком. Можно заметить, что если в какой-то момент число допустимых строк превысило количество оставшихся, то лишние строки можно проигнорировать и таким образом время работы составит O(N * максимальную длину из входного набора).
D. Расписание занятий
Эта задача решается методом динамического программирования:
состоянием динамики будет пара чисел – номер аудитории и количество групп, занимавшихся на первой паре в аудитории с номером не превосходящем текущего, для которых вторая аудитория еще не определена. Для каждого состояния будем перебирать количество групп, у которых вторая пара будет проходить в текущей аудитории. При добавлении ответа из нового состояния, нужно домножить его на соответствующие биномиальные коэффициенты (количество способов выбрать группы, у которых первая пара будет в следующей аудитории - Xi + 1, и количество способов выбрать группы, у которых вторая пара будет в текущей аудитории).
E. Испытание для вождя
Сперва по данной раскраске построим следующий граф: каждой клетке сопоставим вершину того же цвета, что и сама клетка. Между соседними клетками проведем ребро веса 0, если клетки одного цвета, и веса 1, если разного. Теперь для каждой клетки посчитаем кратчайшее расстояния из нее, до самой удаленной черной клетки (обозначим его D). Нетрудно видеть, что можно построить последовательность из D + 1 перекрашивания приводящую к искомой раскраске:
- на первом шаге покрасим все клетки на расстоянии меньше либо равном D в черный цвет
- на втором шаге покрасим все клетки на расстоянии меньше либо равном D - 1 в белый цвет
- и т. д.
Из всех клеток, выберем ту, для которой это расстояние минимально, и это расстояние увеличенное на единицу будет ответом на задачу.
Сперва сожмем все вершины между которыми расстояние равно нулю в одну компоненту (получим граф компонент связности).
Заметим, что если мы перекрашиваем какую-то клетку, то можно перекрасить и всю её компоненту, так как в итоге раскраска не изменится.
1) можно доказать, что любую раскраску можно привести к такому виду, что каждое следующее перекрашивание будет подмножеством предыдущего.
2) последнее перекрашивание будет состоят ровно из одной вершины (возможно целая одноцветная связная область исходной доски).
Поэтому один из оптимальных ответов будет иметь вид описанный в разборе. Если в качестве начальной вершины мы возьмем клетку, лежащую в последнем перекрашивании этого оптимального ответа, алгоритм найдет решению не хуже чем оптимальное.
First, compress all vertices between which distance is equal to zero in one component (get graph of connected components).
Note that if we repaint some cell, it can be repainted and all its component, as a result coloring will not change.
1) we can prove that any coloring can be reduced to a form such that each subsequent repainting is a subset of the previous one.
2) the last repainting will consist of exactly one vertex (possibly the whole monochromatic connected region of the original board).
Therefore, one of the best answers will be of the form described in the review. If as the initial vertex, we take a cell, lying in the last repainting of the optimal sequence, the algorithm finds the solution not worse than optimal.
http://ideone.com/il8Do
http://ideone.com/lHtSZ