534A - Экзамен

Легко убедиться в том, что k = n для всех n ≥ 4. Существует множество алгоритмов, позволяющих построить нужную последовательность длины n при n ≥ 4. Например, можно сажать студентов слева направо, при этом сначала сажать студентов с нечетными номерами в порядке убывания, начиная с самого большого нечетного номера, а затем аналогично ставить студентов с четными номерами. В такой последовательности модуль разности между двумя соседними нечетными (или двумя четными) номерами будет равна 2, а единственная пара соседних нечетного и четного номера будет образовывать разность, большую 3 (поскольку n ≥ 4).

Случаи n = 1, n = 2, n = 3 рассматриваются отдельно, и ответы для них равны 1, 1, 2 соответственно. Асимптотика решения — O(n).

Авторское решение: 10691992

534B - Пройденный путь

Покажем, что в каждую секунду i (0 ≤ i ≤ t - 1) максимально возможная скорость равняется . Действительно, если бы значение v_i было больше, то автомобиль не успел бы разогнаться или затормозить вовремя. Тот факт, что разность между соседними v_i при такой формуле не превышает d по модулю каждый может доказать самостоятельно.

Пользуясь вышеописанной формулой, можно просто перебрать i от 0 до t - 1 и просуммировать значения v_i, получая асимптотику решения O(t).

Возможно написать немного другое решение, которое пользуется следующим фактом. Если до конца пути осталось t секунд, текущая скорость равна u, а скорость в конце должна быть равна v₂, то существует способ доехать до конца пути требуемым образом тогда и только тогда, когда |u - v₂| ≤ t·d. Имея этот критерий существования ответа, можно просто каждый раз пытаться перейти к следующей секунде, выбирая максимальную из скоростей (просто в цикле от u + d до u - d), чтобы из состояния на следующей секунде был способ дойти до конца пути.

Авторские решения: 10692136 и 10692160

534C - Кости Поликарпа

Решение задачи использует факт, что с помощью k костей d₁, d₂, ..., d_k можно набрать любую сумму от k до . Это легко объясняется тем, что если существует способ набрать сумму s > k с помощью костей, то существует способ набрать сумму s - 1, который получается уменьшением значения одной кости на 1.

Обозначим сумму значений всех n костей как . Зафиксируем очередную кость d_i (значение на ней обозначим как x (1 ≤ x ≤ d_i). С помощью остальных костей мы можем набрать сумму s (n - 1 ≤ s ≤ S - d_i). Мы знаем, что общая сумма s + x = A, а значит n - 1 ≤ A - x ≤ S - d_i, откуда следует, что A - (n - 1) ≥ x ≥ A - (S - d_i).

С помощью вышеописанных неравенств для каждой кости вычисляется отрезок возможных значений, с помощью которого вычисляется количество значений, которые выпасть не могли. Асимптотика решения — O(n).

Авторское решение: 10692192

534D - Рукопожатия

Очевидно, порядок чисел в последовательности a значения не имеет. Ниже будем считать, что порядок чисел совпадает с порядком появления в ЦОПП соответствующих студентов (т.е. сначала пришел студент с индексом 1, потом 2 и так далее).

Для того, чтобы итоговая последовательность чисел a_i удовлетворяла условию задачи, необходимо и достаточно, чтобы выполнялись условия a_i + 1 ≤ a_i + 1 и . Для построения такой последовательности можно воспользоваться следующим жадным алгоритмом: первым числом, очевидно, поставим 0, а среди всех возможных вариантов последующих чисел a_i + 1 будем выбирать максимальное, удовлетворяющее вышеописанным условиям (т.е. первое число, меньшее либо равное a_i + 1, имеющее такой же остаток от деления, как и a_i + 1). Корректность такого алгоритма обосновывается тем, что любую правильную последовательность можно привести к такому же виду с помощью перестановки чисел последовательности.

Реализовать такой алгоритм можно, если исходные числа поделить на три части по остатку от деления, и с помощью, например, структуры данных ''множество'' быстро находить следующее число за . Общая асимптотика такого решения — . Решение можно ускорить до линейного, воспользовавшись принципом сжатия путей.

Авторское решение: 10692252

534E - Берляндская система локального позиционирования

Предположим, что автобус начинал движение в остановке с номером 1 и промоделируем отрезок движения автобуса по m остановкам. Посчитаем для каждой из n остановок, сколько раз ее посетил автобус. Проверим, подходят ли эти количества к входным данным и обновим ответ, если нужно. Теперь попробуем сдвинуть стартовую остановку на остановку с номером 2. Поскольку отрезок пути автобуса должен иметь фиксированную длину, сдвинуть вперед нужно и последнюю остановку, смоделировав движение автобуса еще на одну остановку (после последней остановки).

Таким образом, чтобы получить количества остановок, сдвинув стартовую остановку на одну вперед, нужно сделать обновления всего для четырех остановок. Каждый раз, сдвигая стартовую остановку таким образом, нужно обновлять ответ. Стоит учесть, что всевозможных стартовых остановок (учитывая направление движения) ровно 2n - 2.

Асимптотика решения — O(n).

Авторское решение: 10705354

534F - Упрощенный японский кроссворд

Задачу можно решать несколькими способами.

Один из них можно описать следующим образом. Разделим поле кроссворда на две примерно равные части по столбцам (n × k и n × m - k). Решим для каждой части поля задачу отдельно с помощью перебора (который учитывает ограничения на количества блоков в столбцах) с запоминаниями по количествам блоков в строках. Поскольку каждая часть поля, в худшем случае, имеет размер 5 × 10, всевозможных полей с ограничениями на количество блоков будет не очень много. Посчитав все варианты полей для левой и правой половины поля, нужно перебрать левую часть поля и подобрать возможную правую часть (с учетом ограничений на количества блоков в строках). Такое решение требует аккуратной реализации автора.

Так же возможно решение с использованием динамики по профилю, где профиль — количество блоков в строке.

Авторское решение пользуется обеими идеями: 10705343