Идея решения: Нам предлагают идти от конца операции. Давайте определим обратные действия для каждой операции:

1. Если x четное, при обратной операции мы умножаем на 2.
2. Если x нечетное, проверяем, можно ли получить x как (x-1)/3, и если это число нечетное, делим на него.

Алгоритм:

1. Читаем число x.
2. Если оно четное — умножаем на 2.
3. Если нечетное — проверяем условие (x-1)/3 и делим, если подходит.
4. Выводим результат.

Идея решения: Пусть нам дан массив, и мы хотим гарантировать gcd(array) = n, где массив — перестановка.

Замечаем: любое число x < n можно превратить в n, добавив n-x.

Алгоритм:

1. Для каждого элемента a[i]:

• Если a[i] = n, добавляем n.
• Иначе добавляем n-a[i].

1. Новый массив — ответ.

Идея решения: Рассмотрим ситуации, когда решение невозможно:

1. a четное, а b нечетное.

• Даже если разделить b на его делитель, b останется нечетным, а a четное — сумма a+b никогда не станет четной.

1. a нечетное, b четное, но (b/2) нечетное.

• Любой делитель b, умножая a, даст четное число, но при этом сумма не получится четной.

Иначе:

1. Если оба числа нечетные — берем делитель d = b, b/b = 1.
2. Иначе — берем d = b/2, чтобы получить максимальную четную сумму.

Идея решения: Проверим, когда ответ невозможен:

Если f(x) ≥ x и f(x) % x != 0, корректного расположения нет.

Пример: Массив [2,2,3,3,3,2]

f(2) = 3, f(3) = 3

Можно попытаться составить массив [1,1,2,2,2,3], но последняя тройка не совпадает с a[n] = 2 → решения нет

Если таких ситуаций нет, решение всегда существует:

Группируем одинаковые числа.

Ставим их на позиции, соответствующие их количеству.

Если f(x) > x, начинаем с стартового числа st = 1, кладем x раз, затем обновляем st и продолжаем.

Идея решения: Наблюдение: после трёх операций массив стабилизируется.

Пример:

[0,2,1,2,3,8] -> [0,4,1,4,3,4] -> [0,2,1,2,2,2] -> [0,3,1,3,3,3] -> [0,2,1,2,2,2]

• После третьей операции массив больше не меняется.
• Достаточно посчитать суммы после 1-й, 2-й и 3-й операций.

Вывод:

• Если k = 1 — берем сумму после первой операции.
• Если k четное — берем сумму после второй операции.
• Иначе — берем сумму после третьей операции.