Массивы Росомахи: математическая ловкость и фантазия

Авторы задачи и разработчики: Антон Вдовин и Даниил Орешников

Сделаем несколько наблюдений:

  1. из любых трех подряд идущих чисел будет не более одного четного; следовательно, не более $$$\frac{n}{3}$$$ чисел будут четными;
  2. если нечетные числа расположить подряд, то они всегда будут удовлетворять условию: действительно, разница между двумя нечетными числами на расстоянии не больше двух будет четной и будет не превосходить $$$4$$$, следовательно, общих делителей у них не будет.

Докажем, что в большей части случаев задача решается и для $$$n \ge \frac{3m}{4}$$$. Для этого достаточно построить массив, содержащий все нечетные числа от $$$l$$$ до $$$r$$$ и ровно половину четных. Сначала расставим нечетные: это логично сделать в соответствии с наблюдением выше, упорядочив их подряд. Оставим при этом каждое третье место под какое-то четное число. Получим последовательность вида $$$$$$1, 3, ?, 5, 7, ?, 9, 11, ?, 13, 15, \ldots$$$$$$ (здесь для примера взято $$$l = 1$$$). Как расположим четные числа? Заметим, что чтобы каждое четное было различным, достаточно расположить на месте $$$?$$$ четные, равные полусумме стоящих рядом нечетных. То есть: $$$$$$1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, \ldots \text{,}$$$$$$ но такое распределение не работает — на расстоянии $$$2$$$ оказались числа $$$12$$$ и $$$9$$$.

Исправим возникшую проблему:

Остается только заметить, что если $$$t$$$ делилось на $$$3$$$, то ни $$$t - 2$$$, ни $$$t + 2$$$ не делятся на $$$3$$$, а также хотя бы одно из них не делится на $$$5$$$. Выберем его и поставим вместо $$$t$$$. В итоге мы использовали все нечетные и ровно половину четных, то есть ровно $$$\frac{3m}{4}$$$ различных чисел.

Чтобы решить исходную задачу, повторим тот же шаблон, пока числа не закончатся, а затем просто зациклим последнюю тройку: $$$x, y, z, x, y, z, \ldots$$$. С учетом округления вниз и $$$-1$$$ в требовании к количеству различных чисел, такое решение проходит все тесты.