Что-то мне подсказывает, что он будет проводиться по задачам СПбКОШП :)

"Как только ИТМО выдаст пароли — вышлю", (с) Артем Игликов

Идея в целом — динамическое программирование. введем динамику dp[i][j] = rage. i — сколько первых полос машин обработали. j — сколько в сумме пропустили машин за один проход. rage — минимальная суммарная ярость за все время водителей первых i полос. Если пропускать с этих первых i полос по j машин то база динамики — dp[0][0] = 0. Переходы — dp[i][j] = min(dp[i-1][j-k] + rage(i,k)), k = 1..j , где rage(i,k) — суммарная ярость водителей i-oй полосы за все время, если гнать по k машин за один проход то в отдельной матрице previ сохраняем оптимальный переход. Потом по этому массиву восстанавливаем ответ.

Работает за O(n*(k^2)).

Когда день рождения у Шерил? Баянище среди математиков :)

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

Будем рассматривать “common knowledge”, т.е. факты, известные всем, кто наблюдает комментарии Ани и Бори.

Первое утверждение Ани: “Я не знаю точную дату рождения Вани, но я уверена, что и Боря её тоже не знает”. После него все узнают следующее: для числа, которое знает Аня, существует несколько (> 1) подходящих месяцев (поскольку она не знает точную дату), притом для каждого из этих месяцев существует несколько (> 1) подходящих дней (поскольку она говорит, что точно знает, что Бориной информации недостаточно). Назовём все дни (= числа 1..31), которые подходят под это условие, Аниными днями (NB: их много! среди них точно есть день, который Ваня назвал Ане, но есть и левые).

Первое утверждение Бори: “Я сначала не знал дату Ваниного рождения, но теперь, после твоего комментария, знаю точно!”. Узнаём следующее: для месяца, который знает Боря, существует несколько подходящих дней, но ровно один из этих дней является Аниным днём. Назовём все такие месяца Бориными месяцами (аналогичная NB).

Второе утверждение Ани: “Ого! Теперь и я тоже знаю точную дату!”. То есть среди месяцев, которые соответствуют известному Ане дню (который точно является Аниным днём), есть только один Борин месяц. Назовём все Анины дни, для которых это верно, эээ, супераниными днями.

Поскольку мы формализовали всю доступную нам информацию и известно, что с её помощью можно однозначно определить день рождения Вани, существует ровно одна пара (супераниндень, Борин месяц), которую можно найти в инпуте. Её и выведем.

Разделим a на 2 части, каждое будет максимум до миллиона. В первой части для каждого остатка от деления на b запишем минимальное количество измененных цифр, для второй части доберем остаток от деления из первой. O(sqrt(N)). Подсказывают, что если вначале перебирать вторую половину можно обойтись без map, так как остатки от деления на b не превысят корня.

Мы делали так: если M до 10⁴, то, очевидно, что среди n...n + 10000 есть хоть одно число, которое делится на M, поэтому в ответе изменено не более 4 цифр, их можем перебрать (C[11, 4] × 10⁴ = 3300000, норм). Если же M больше, чем 10⁴, то существует где-то подходящих кратных M, можем попробовать каждый из них.

Если M <= 10^6, можно написать динамику dp[len][mod], иначе просто перебираем все числа кратные M.

Всё еще frozen.

вот окончательные результаты Казахстана

Вот код: pastie.

В целом идея такова: ставим на строку в промежутке [rb — 10^5, rb + 10^5]. Каждую строку делим на полоски по запрещенным, и в каждой решаем отдельно.

Допустим, что нам известно, что места с a-того по b-тое в ряду r свободны, и мы хотим найти в них неудачность оптимального расположения для k шушпанчиков (r - l + 1 ≥ k).

Интуитивно понятно, что есть три возможных оптимальных варианта расположения: так, что c_b находится посередине выбранного отрезка (в случае чётного k этот случай распадается на два) или так, что отрезок касается одной из границ отрезка a... b. Любой другой отрезок длины k можно подвинуть влево или вправо, и это уменьшит его неудачность.

Неудачность считаем отдельно по рядам и по колонкам. Каждое из этих мест находится на расстоянии |r - r_b| по рядам от лучшего, так что общая неудачность по рядам — |r - r_b| × k. А по колонкам получается либо одна арифметическа прогрессия (если r_b строго слева или строго справа обеих границ выбранного отрезка), либо две (если r_b принадлежит выбранному отрезку).

Существует не более 10⁵ рядов, в которых есть занятые места — можем отсортировать занятые места, и тогда каждый ряд разобьём на некоторое количество свободных отрезков (в сумме порядка 10⁵ отрезков), оптимальное расположение в каждом из которых можем посчитать (за константное время) так, как описано выше.

Остаётся порядка 10⁹ рядов, в которых не занято ни одно место, но ясно, что нас интересует только тот свободный ряд, который ближе всех к лучшему месту — можем завести булевский массив [-100000..100000], который будет соответствовать рядам на расстоянии не более 100000 от ряда лучшего места, и во время чтения отмечать все ряды, в которых занято хоть одно место — поскольку занято только 10⁵ мест, то в этом массиве сможем найти самый близкий совершенно пустой ряд. Его тоже проверим так, как описано выше (положив a = 1, b = n).

Попробуем решать стандартную задачу, то есть просто искать Гамильтонов цикл минимального веса (это делается стандартной динамикой f[mask][last]).
Сделаем только одну модификацию: заметим, что после того, как в mask
есть какое-то количество единичных битов (обозначим за cnt) такое, что
cnt есть сумма размеров нескольких первых групп, то нужно вернуться в 0 (это значит, что
очередной человек завершил свой обход).
Код: http://ideone.com/J0S8DC

Любопытно: в условии задачи E написано «Леша уже попробовал решить пример, но, неожиданно для себя, понял, что n на m не делится.», однако в тестах 29, 30, 35, 36, 41 и 42 это условие не выполняется.