408925: GYM103382 3 Игра
Description
На уроке информатики учитель предложил Васе сыграть в следующую игру.
На доске записаны по порядку все целые числа от $$$1$$$ до $$$N$$$. За один ход можно стереть либо все числа, стоящие на чётных позициях, либо все числа, стоящие на нечётных позициях. После этого оставшиеся числа перенумеровываются заново слева направо; нумерация начинается с единицы.
Игра продолжается, пока на доске есть хотя бы два числа.
Вася выиграет, если после окончания игры единственным оставшимся на доске числом будет число $$$X$$$. Выведите последовательность ходов, которая приведёт к победе Васи. Гарантируется, что Вася всегда может победить.
Входные данныеВ первой строке содержится целое число $$$N$$$ $$$\left(2 \le N \le 10^{9}\right)$$$ — начальное количество чисел на доске.
Во второй строке содержится целое число $$$X$$$ $$$\left(1 \le X \le N \right)$$$ — число, которое должно остаться в конце игры.
Выходные данныеВыведите последовательность целых чисел, состоящую из чисел $$$1$$$ и $$$2$$$ — ходов Васи. Число $$$1$$$ означает, что Вася стирает все числа на нечётных позициях, число $$$2$$$ — на чётных.
Каждый ход Васи выводите на отдельной строке.
Система оценкиВ этой задаче $$$20$$$ тестов, не считая тестов из условия. За каждый пройденный тест будет начисляться $$$5$$$ баллов.
На тесты наложены следующие ограничения:
Номера тестов | Дополнительные ограничения |
1 — 2 | Тесты из условия |
3 — 10 | $$$N \le 1000$$$ |
11 | $$$X = 1$$$ |
12 — 14 | $$$X = N$$$ |
15 — 22 | без дополнительных ограничений |
10 5Выходные данные
2 2 1Входные данные
6 6Выходные данные
1 2 1Примечание
Рассмотрим первый пример. На доске записаны числа:
$$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6$$$ $$$7$$$ $$$8$$$ $$$9$$$ $$$10$$$
Первым ходом Вася стирает все числа на чётных позициях, на доске остаются числа:
$$$1$$$ $$$3$$$ $$$5$$$ $$$7$$$ $$$9$$$
Затем позиции оставшихся чисел перенумеровываются — то есть оставшиеся после первого хода Васи числа получат номера от $$$1$$$ до $$$5$$$. Вторым ходом Вася снова удаляет все числа на чётных позициях, на доске остаются числа:
$$$1$$$ $$$5$$$ $$$9$$$
Третьим ходом Вася удаляет все числа на нечётных позициях, и на доске останется только число $$$5$$$, которое и было нужно.
Во втором примере выписаны числа:
$$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6$$$
Вася стирает числа на нечётных позициях, остаются:
$$$2$$$ $$$4$$$ $$$6$$$
Вася стирает число $$$4$$$, которое стоит на чётной позиции. Остаются:
$$$2$$$ $$$6$$$
Вася стирает число $$$2$$$, которое стоит на нечётной позиции. Осталось число $$$6$$$.