Новичок
Новичок
- Статус
- Оффлайн
- Регистрация
- 28 Окт 2021
- Сообщения
- 1
- Реакции
- 0
Задача 7: Игра
На уроке информатики учитель предложил Васе сыграть в следующую игру.
На доске записаны по порядку все целые числа от 1 до N. За один ход можно стереть либо все числа, стоящие на чётных позициях, либо все числа, стоящие на нечётных позициях. После этого оставшиеся числа перенумеровываются заново слева направо; нумерация начинается с единицы.
Игра продолжается, пока на доске есть хотя бы два числа.
Вася выиграет, если после окончания игры единственным оставшимся на доске числом будет число X. Выведите последовательность ходов, которая приведёт к победе Васи. Гарантируется, что Вася всегда может победить.
Входные данные
В первой строке содержится целое число N (2 ≤ N ≤ 109) — начальное количество чисел на доске.
Во второй строке содержится целое число X (1 ≤ X ≤ N) — число, которое должно остаться в конце игры.
Выходные данные
Выведите последовательность целых чисел, состоящую из чисел 1 и 2 — ходов Васи. Число 1 означает, что Вася стирает все числа на нечётных позициях, число 2 — на чётных.
Каждый ход Васи выводите на отдельной строке.
Система оценки
В этой задаче 20 тестов, не считая тестов из условия. За каждый пройденный тест будет начисляться 5 баллов.
На тесты наложены следующие ограничения:
Примеры
На уроке информатики учитель предложил Васе сыграть в следующую игру.
На доске записаны по порядку все целые числа от 1 до N. За один ход можно стереть либо все числа, стоящие на чётных позициях, либо все числа, стоящие на нечётных позициях. После этого оставшиеся числа перенумеровываются заново слева направо; нумерация начинается с единицы.
Игра продолжается, пока на доске есть хотя бы два числа.
Вася выиграет, если после окончания игры единственным оставшимся на доске числом будет число X. Выведите последовательность ходов, которая приведёт к победе Васи. Гарантируется, что Вася всегда может победить.
Входные данные
В первой строке содержится целое число N (2 ≤ N ≤ 109) — начальное количество чисел на доске.
Во второй строке содержится целое число 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 | без дополнительных ограничений |
| Ввод | Вывод | Пояснение |
|---|---|---|
| 10 5 | 2 2 1 | На доске записаны числа: 1 2 3 4 5 6 7 8 9 10 Первым ходом Вася стирает все числа на чётных позициях, на доске остаются числа: 1 3 5 7 9 Затем позиции оставшихся чисел перенумеровываются — то есть оставшиеся после первого хода Васи числа получат номера от 1 до 5. Вторым ходом Вася снова удаляет все числа на чётных позициях, на доске остаются числа: 1 5 9 Третьим ходом Вася удаляет все числа на нечётных позициях, и на доске останется только число 5, которое и было нужно. |
| 6 6 | 1 2 1 | Во втором примере выписаны числа 1 2 3 4 5 6 Вася стирает числа на нечётных позициях, остаются 2 4 6 Вася стирает число 4, которое стоит на чётной позиции. Остаются 2 6 Вася стирает число 2, которое стоит на нечётной позиции. Осталось число 6. |
