Задача A. Покупка велосипеда.

Идея: Виталий Аксёнов.
Реализация: Дмитрий Филиппов.
Разбор: Дмитрий Филиппов.

По условию задачи нужно сказать, можно ли по данным числам a, b, c найти такие числа a₁, b₁, что a₁  ≤  a, b₁  ≤  b и a₁ + 2 · b₁ = c.

Решение у этой задачи простое: почти всегда достаточно проверить, что суммарный номинал наших монет не меньше c: a + 2 · b  ≥  c. Исключение — когда c нечётное. Тогда ещё нужно проверить, что a  ≥  1.

Задача B. Цифровые корни.

Идея: Григорий Шовкопляс.
Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.

В этой задаче нужно по числам a и b определить, какие из значений цифрового корня встретятся на этом отрезке наибольшее количество раз.

Заметим, что у цифрового всего девять значений, а также они циклически повторяются. Таким образом, нужно вычислить только цифровые корни от a и b, а чаще всего встречаются цифры между значениями этих цифровых корней. Единственное, что нужно было дополнительно учесть — это случай, когда цифровой корень a больше чем цифровой корень b. Также нужно было не забыть, что ответ нужно выводить по возрастанию.

Задача C. Две улитки.

Идея: Дмитрий Филиппов.
Реализация: Николай Ведерников.
Разбор: Николай Ведерников.

В этой задаче две улитки днём поднимаются на a_i, а ночью опускаются на b_i. Требуется определить, сколько по времени первая улитка обгоняла вторую.

Задача решается моделированием. Рассматриваем часы последовательно. Для начала узнаем сейчас день или ночь. Посмотрим положение улиток до начала этого часа и после. Если до начала часа одна была выше другой, а после окончания часа, также была выше, то обгона не было. Тогда, если выше была первая, то к ответу добавим один час. Если же в начале часа была выше, а потом ниже, следовательно одна обогнала другую. Для того, чтобы узнать время, когда одна обгонит другую, надо посчитать расстояния между ними и поделить на разницу скоростей. После этого добавить к ответу время, в когда первая улитка была выше второй в этот час.

Задача D. Игровые автоматы.

Идея: Анна Малова.
Реализация: Виталий Аксёнов.
Разбор: Виталий Аксёнов.

Нам даны кнопки, которые умеют выключать какой-то набор из лампочек, и кнопки, которые умеют включать какой-то набор лампочек. Задача: с помощью кнопок перевести лампочки из выключенного состояния в заданнное, или сообщить, что такое сделать нельзя.

Сначала, поймём, что дважды нажимать одну и ту же кнопку не имеет смысла, так как мы всегда можем оставить только последнее её нажатие, и конечное состояние не изменится. Далее, рассмотрим задачу с конца. У каждой лампочки будет три состояния: включена, выключена и неизвестно. Когда мы обращаем нажатие кнопки, помечаем все лампочки, за которые она отвечала, что их состояние неизвестно.

Мы могли нажимать кнопку, если:

• кнопка выключает лампочки, то состояния изменённых лампочек должны быть или выключены, или неизвестны;
• кнопка включает лампочки, то состояния изменённых лампочек должны быть или включены, или неизвестны.

Смотрим на последнее состояние, и нажимаем кнопки, каждую по одному разу, если это возможно. Пусть ни одну кнопку нажать нельзя, то нужно проверить, правда ли лампочки или выключены, или неизвестны, что соответствует стартовому состоянию. Если правда, мы можем последовательностью нажатий перейти в заданное состояние, иначе — нельзя.

Задача E. Интернетопровод.

Идея: Виталий Аксёнов.
Реализация: Илья Збань.
Разбор: Илья Збань.

В задаче дано n точек, и нужно найти некоторую прямую l и расстояние d такие, что количество точек, расположенных ровно на расстоянии d от прямой l было максимально.

Любая прямая задается тройкой коэффициентов a, b и c таких, что ax+by+c=0. Две прямые (a₁, b₁, c₁) и (a₂, b₂, c₂) параллельны, если коллинеарны векторы (a₁, b₁) и (a₂, b₂).

Проведем прямые через все пары точек, и приведем их к нормальному виду: GCD(a, b)=1, и a>0 или a=0 и b>0. Такое представление единственно для любой прямой. Перебрав все прямые, проходящие через пару точек, мы получим все углы, под которыми есть смысл проводить прямую-ответ (в случае, когда ответ больше двух, какие-то две точки из ответа будут лежать на одной прямой). Зная угол, под которым проходит прямая-ответ, несложно указать оптимальное d: для фиксированных a, b, задающих угол наклона прямой, нужно выбрать два самых часто встречаемых с этими значениями a, b значения c, и мы получим две прямые, параллельные искомой, находящиеся от нее на расстоянии d. В случае, если такое значение c всего одно, то, если не все точки лежат на одной прямой, можно добавить к ответу еще одну точку.