Воссоединение c Веномом

Автор задачи: Даниил Орешников, разработчик: Константин Бац

Заметим, что любое любое изменение показателей не меняет их разницу по модулю 2. Докажем это. Возьмем два любых показателя гормонов $$$a_i$$$ и $$$a_j$$$ и применим к ним некоторое изменение.

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

Пусть нам даны 3 характеристики $$$a_1 \leqslant a_2 \leqslant a_3$$$, которые не уравновешены, но их можно уравновесить. Ясно, что, чтобы сделать это за минимальное количество действий, стоит уменьшить $$$a_3$$$ на один и увеличить $$$a_1$$$ и $$$a_2$$$ на один. Это оптимально, так как любое другое действие только увеличит разницу между показателями. Таким образом, оптимальную стратегию уравновешивания показателей можно представить так:


while a[1] != a[2] or a[2] != a[3]:
a.sort()
a[1] += 1
a[2] += 1
a[3] -= 1

Понятно, что такое решение является не оптимальным. Давайте заметим, что каждая итерация в цикле с точки зрения разности между показателями равносильна $$$a_3 = a_3 - 2$$$. Тогда все итерации можно представить как уменьшение $$$a_3$$$ до тех пор, пока оно не станет равно $$$a_1$$$, и уменьшение $$$a_2$$$ до тех пор, пока оно тоже не станет равно $$$a_1$$$. В таком случае мы совершим $$$\cfrac{a_3 - a_1}{2} + \cfrac{a_2 - a_1}{2}$$$ изменений. Заметим, что обе разности поделятся нацело, так как все три показателя изначально равны по модулю 2. Это число и есть ответ на задачу.

Итак, решение задачи: проверим, что показатели гормонов равны по модулю два — если равенства нет, то ответ равен $$$-1$$$, иначе отсортируем по возрастанию три показателя и выведем ответ $$$\cfrac{a_3 - a_1}{2} + \cfrac{a_2 - a_1}{2}$$$. Время работы решения — $$$\mathcal{O}(1)$$$.