Помощь с олимпиадой.

[Leo123456789]

Сдать решение задачи 7-Игра

Полный балл:	100
Ограничение времени:	1 с
Ограничение памяти:	512M
Ограничение размера стека:	64M

Задача 7: Игра
На уроке информатики учитель предложил Васе сыграть в следующую игру.

На доске записаны по порядку все целые числа от 1 до N. За один ход можно стереть либо все числа, стоящие на чётных позициях, либо все числа, стоящие на нечётных позициях. После этого оставшиеся числа перенумеровываются заново слева направо; нумерация начинается с единицы.

Игра продолжается, пока на доске есть хотя бы два числа.

Вася выиграет, если после окончания игры единственным оставшимся на доске числом будет число X. Выведите последовательность ходов, которая приведёт к победе Васи. Гарантируется, что Вася всегда может победить.

Входные данные
В первой строке содержится целое число 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	без дополнительных ограничений

Примеры

Ввод	Вывод	Пояснение
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.

 

[noth1ng]

При чем тут питон если это просто глупая олимпиада?..

 

[CoffeMan]

блять заебали какая олимпиада в 9 часов вечера

 

[Resent]

Вот решение на C++ .

#include <iostream>

using std::size_t, std::cin, std::cout;

int main()
{
    size_t n, x;
    cin >> n >> x;
    size_t l = x - 1, r = n - x;

    while (l + r > 0) {
        cout << 2 - l % 2 << '\n';
        l /= 2;
        r /= 2;
    }
}

Если хочешь попасть на этап выше, стоит попробовать решить и самому =)

 

[Irval]

#include <iostream>

using namespace std;

int main() {
    long long N, X;
    cin >> N >> X;

    while (N != 1) {
        bool isEv = X % 2;
        cout << (isEv ? 2 : 1) << endl;
       
        int newN = N / 2;
        if (isEv && N % 2) newN++;
        N = newN;

        int newX = X / 2;
        if (isEv && X % 2) newX++;
        X = newX;
    }
}

Сложность - O(logN).
https://yougame.biz/threads/230162/ - решения всех задач с Вашей олимпиады. Что там можно было решать несколько часов - я не знаю.