Содержится целое число N (2 ≤ N ≤ 10^9) — начальное количество чисел на доске.

Во второй строке содержится целое число X (1 ≤ X ≤ N) — число, которое должно остаться в конце игры.

Выходные данные
Выведите последовательность целых чисел, состоящую из чисел 1 и 2 — ходов Васи. Число 1 означает, что Вася стирает все числа на нечётных позициях, число 2 — на чётных.

Каждый ход Васи выводите на отдельной строке.

Система оценки
В этой задаче 20 тестов, не считая тестов из условия. За каждый пройденный тест будет начисляться 5 баллов.

На тесты наложены следующие ограничения:
Номера тестов | Дополнительные ограничения
1 – 2 | Тесты из условия
3 – 10 | N ≤ 1000
11 | X = 1
12 – 14 | X = N
15 – 22 | без дополнительных ограничений

Решение задачи (C++17)

Идея решения

Изначально на доске находятся числа от 1 до N. Необходимо выполнять ходы так, чтобы в конце осталось только число X.

На каждом ходу Вася может выбрать один из двух вариантов:

• 1 — стереть числа, стоящие на нечётных позициях. Тогда останутся числа на чётных позициях.

• 2 — стереть числа, стоящие на чётных позициях. Тогда останутся числа на нечётных позициях.

После каждого хода позиции оставшихся чисел нумеруются заново, начиная с единицы.

Нам нужно отслеживать две величины:

• n — текущее количество чисел на доске;

• x — текущая позиция числа, которое необходимо сохранить.

Алгоритм

Пока на доске находится больше одного числа, выполняем следующие действия:

1. Если x нечётное:

Нужно выбрать ход 2, поскольку он оставляет числа на нечётных позициях.

После этого:

• Новая позиция искомого числа: x = (x + 1) / 2.

• Новое количество чисел: n = (n + 1) / 2.

2. Если x чётное:

Нужно выбрать ход 1, поскольку он оставляет числа на чётных позициях.

После этого:

• Новая позиция искомого числа: x = x / 2.

• Новое количество чисел: n = n / 2.

Повторяем действия, пока n не станет равным единице.

Все выбранные ходы выводим по одному на строке.

Код решения (C++17)

#include 
using namespace std;
int main() {
    long long n, x;
    cin >> n >> x;
    while (n > 1) {
        if (x % 2 == 1) {
            cout << 2 << '\n';
            x = (x + 1) / 2;
            n = (n + 1) / 2;
        } else {
            cout << 1 << '\n';
            x = x / 2;
            n = n / 2;
        }
    }
    return 0;
}

Пример работы алгоритма

Пусть N = 10, X = 7.

Изначально на доске:

1 2 3 4 5 6 7 8 9 10

Число 7 находится на нечётной позиции, поэтому выбираем ход 2.

После первого хода остаются:

1 3 5 7 9

Теперь число 7 находится на четвёртой позиции. Выбираем ход 1.

После второго хода остаются:

3 7

Число 7 находится на второй позиции. Выбираем ход 1.

После третьего хода остаётся:

7

Таким образом, ответ:

Доказательство корректности

Рассмотрим положение искомого числа перед каждым ходом.

Если его позиция нечётная, ход 2 гарантированно сохраняет это число, поскольку стираются только числа на чётных позициях. После удаления его новая позиция равна (x + 1) / 2.

Если его позиция чётная, ход 1 гарантированно сохраняет это число, поскольку стираются только числа на нечётных позициях. Его новая позиция равна x / 2.

Таким образом, на каждом шаге выбранный ход сохраняет искомое число.

Кроме того, количество чисел на доске после каждого хода уменьшается примерно в два раза. Поэтому процесс обязательно завершится, когда останется одно число.

Поскольку искомое число не удаляется ни на одном шаге, единственным оставшимся числом будет именно X.

Следовательно, алгоритм всегда строит корректную последовательность ходов.

Сложность алгоритма

• Временная сложность: $O(\log N)$, поскольку количество чисел на каждом шаге уменьшается примерно в два раза.

• Дополнительная память: $O(1)$, поскольку используются только две переменные n и x.

При ограничении $N \leq 10^9$ потребуется не более 30 ходов, поэтому алгоритм с большим запасом укладывается в ограничения задачи.