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



Задача A. Лифт.
Автор --- Кудряшов Игорь.

Данная задача является утешительной задачей контеста. В ней нужно рассмотреть 4 случая. Если пассажир зашел через переднюю дверь и держался за 1ый поручень, или он зашел через заднюю дверь и держался за 2ой поручень, то нужно выдать сообщение о том, что он левша. Если же пассажир зашел через переднюю дверь и держался за 2ой поручень, или он зашел через заднюю дверь и держался за 1ый поручень, то пассажир является правшой.

Задача B. Что? Где? Когда?
Автор --- Бондаренко Полина.

Условие задачи можно переформулировать следующим образом: найти первую справа 1 в зацикленном массиве, если в ячейке с номером k стоит 0.
От ячейки с номером k движемся направо по массиву, пока не встретим ячейку с 1 или не закончится массив. Если дошли до конца массива, а 1 еще не встретили, то начинаем идти с начала. Т.к. по условию гарантируется, что хотя бы одна единица существует, то за один проход мы найдем ячейку с единицей.

Задача C. Винни-Пух и мед.
Автор --- Матов Дмитрий.

В этой задаче требуется промоделировать процесс поедания меда Винни-Пухом. Чтобы это сделать, нужно хранить для каждой банки количество оставшегося в ней меда, а также количество раз, которое Винни уже ел из этой банки. Можно решить задачу и проще: заметим, что не имеет значения, в каком порядке Винни-Пух ест мед из банок. Поэтому все банки можно обрабатывать по-отдельности. Тогда отпадает необходимость в моделировании: для каждой банки сразу можно понять, сколько меда в ней останется. Пусть в банке изначальн X килограмм меда. Тогда, если X ≥ 3k, то Винни-Пух съест из этой банки 3k, а останется X - 3k. Если же X < 3k, то в банке останется килограмм меда.

Задача D. Три сына.
Автор --- Николай Кузнецов.

По условию задачи требуется разделить поле на три части так, чтобы
суммарное количество кукурузы в первой, во второй и третьей частях
было равно A, B, C. Кроме того, следует обратить внимание, что
порядок, в котором достигается равенство, не важен.

Эта задача достаточно проста. Можно перебрать все способы разрезать
поле по вертикали, все способы разрезать по горизонтали и подсчитать
количество из них тех, которые разрезают поле на части A, B, C.
Очевидно, что разрезов суммарно O(n² + m²). Суммарное количество
кукурузы можно подсчитать за время O(nm). Итого, наше решение имеет
время работы, пропорциональное 4-ой степени от n и m, но при данных
ограничениях это годится.

Задача E. Поставь коня!
Автор --- Агапов Геральд.

Заметим, что в этой игре выигрыш зависит от четности n. Если n четно, выигрывает второй игрок, если нечетно --- первый.

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

В случае нечетного n первый игрок может поставить первым ходом коня в центр поля, а дальше ходить симметрично ходам второго игрока.

Задача F. Пауки.
Автор --- Бондаренко Полина.

Рассмотрим решение задачи для одного паука.
Паук представляет собой граф - --дерево. Решением задачи для него будет длина максимального пути в дереве (или диаметр). Диаметр в дереве можно найти несколькими способами. Один из них --- посчитать от каждой вершины расстояние до каждой и выбрать максимум из этих величин, т.к. граф --- дерево. Асимптотика решения O(n²), где n --- количество вершин в дереве.
Решив задачу для каждого паука, складываем найденные диаметры --- это и будет ответ на задачу.


Задача H. Краткость --- сестра таланта.
Автор --- Холкин Павел.

В данной задаче нужно построить взамно однозначное соответствие одного множества на другое. В данном случае в качестве первого выступает множество исходных слов, а в качестве второго --- множество их сокращений. Обычно такие задачи решаются при помощи нахождения максимального паросочетания. Построим следующий двудольный граф: вершинам первой доли будут соответствовать исходные строки, а вершинам второй --- их сокращенные аналоги. Сокращенные аналоги для исходных строк сгенерируем следующим образом: для каждого слова i исходного множества переберем всевозможные подпоследовательности длины от единицы до четырех. Каждому полученному слову присвоим уникальный номер j, которое будет являться номером соответствующей вершины во второй доле. При этом, разумеется, если полученное слово уже являлось сокращенным аналогом какого-то другого слова из исходного набора, то просто возьмем уже присвоенный ему ранее номер. Теперь добавим ребро (i, j) в наш двудольный граф, которое будет означать, что i-ое слово из набора можно сократить каким-то j-ым сокращением, которое мы сгенерировали. В этом графе найдем максимальное паросочетание, например, алгоритмом Куна. Если в результате для каждой вершины первой доли нашлась пара, значит ответ существует и для каждого слова нужно вывести найденное его сокращение. В противном случае нужно вывести -1.


Задача I. Счастье в числах.
Автор --- Матов Дмитрий.

Обозначим левую половину билета за x = x₁, x₂... x_n, правую за y = y₁, y₂... y_n. Пусть счастливость заданного билета равна h. Попытаемся сначала найти искомый билет среди таких, у которых левая половина равна x.

Будем перебирать по убыванию l (от n - 1 до 0) --- длину префикса второй половины, которая будет совпадать у заданного билета и у искомого. Затем переберем цифру в позиции l + 1 искомого билета. Перебирать цифру будем в порядке возрастания, причем будем рассматривать только цифры, большие, чем y_l + 1. Зафиксировав таким образом первые l + 1 цифру в правой половине искомого билета, будем жадно достраивать его лексикографически минимальным способом с учетом того, что его счастливость должна быть больше h. Более подробно: будем перебирать очередную цифру по возрастанию. Для того, чтобы проверить, можно ли ее поставить, нам нужно быстро посчитать максимальную счастливость, которую мы можем получить, расставляя цифры в конце. Для этого мы должны предположить, что заполним хвост восьмерками. Нужно научиться считать это за O(1).

Если не удалось жадно построить ответ описанным образом, то это значит, что нужно искать среди билетов, у которых левая часть отлична от x. Заметим, что билет, у которого левая часть совпадает с правой, т.е. билет вида zz имеет максимальную счастливость среди всех билетов с левой половиной z. Поэтому сначала найдем билет вида zz такой, что его номер больше xy, и счастливость больше h. Сделаем это жадно: переберем длину t совпадающего префикса у x и h в порядке убывания, попробуем поставить в позицию z_t + 1 цифру большую, чем x_t + 1, а затем будем пытаться дополнить z лексикографически минимальным способом с учетом того, чтобы суммарное число подсвеченных сегментов в z (т.е. счастливость билета zz) было больше h. Если нам это удалось, то правую часть билета можно также достроить жадно, используя аналогичные рассуждения.

Задача J. Минимальная сумма.
Автор --- Агапов Геральд.

Запишем сумму двух векторов v = (x₁, y₁) и u = (x₂, y₂) : s = v + u = (x₁ + x₂, y₁ + y₂).
Длина вектора s есть |s| = (x₁ + x₂)² + (y₁ + y₂)². Понятно, что как ни расставляй знаки у координат,
минимальным значение длины будет в случае, когда s = (|x₁| - |x₂|)² + (|y₁| - |y₂|)².

Таким образом наша задача равносильна следующей: перевести все векторы в первую четверть (сделать координаты неотрицательными), и далее найти два вектора, длина разности которых минимальна, что в свою очередь равносильно нахождению двух ближайших точек на плоскости. Существует вполне известный алгоритм, который с помощью метода "разделяй и властвуй" находит две ближайшие точки за O(n· log(n)).