В условии была описана игра для двух игроков. Состояние игры описывалось одним числом x, и игроки по очереди могли сделать один из двух ходов: заменить x на x + 1, либо на 2x. Тот игрок, который первым написал число, большее, чем n, проиграл, Следовало найти k по возрастанию число x, такое, что первый игрок имеет выигрышную стратегию, если начальное число равнялось x.

Поскольку ограничения на n были достаточно большие, надо было понять структуру чисел, являющихся выигрышными позициями для игрока, который начинает из такого состояния. Мы покажем, что это множество представляется в виде объединения O(logn) отрезков подряд идущих чисел, в каждом из которых либо каждое число, либо каждое второе число это выигрышная позиция для первого игрока.

Будем строить это множество рекурсивно. Пусть процедура F(n) возвращает множество всех таких отрезков, и при этом выполняется инвариант: игрок, сделавший ход в число, большее n, проигрывает.

Рассмотрим два случая. Пусть n нечетно. Тогда любое четное число от 2 до n - 1 это выигрышная позиция, а любое нечетное — проигрышная. Покажем, что первый игрок всегда может сделать так, что он всегда ходит из четной позиции, а его противник — из нечетной. Действительно, если первый игрок переводит x в число x + 1, то второй игрок может перевести x + 1 только в четное число. Осталось лишь заметить, что число n нечетно, и поэтому первый игрок всегда имеет ход, который не приводит к его поражению. Продолжая по индукции, получаем, что если первый игрок начинает с четного числа, то у него есть выигрышная стратегия. В случае, когда первый игрок начинает с нечетного числа, второй игрок использует ту же стратегию и выигрывает.

Теперь пусть n четно. Все нечетные позиции, большие n/2 выигрышны, поскольку удвоение такого числа сразу приводит к поражению, а в таком случае, выигрышная ли позиция, определяется четностью числа оставшихся ходов. Заметим также, что позиция n/2 выигрышна, поскольку из n/2 можно получить n, и другой игрок обязательно превышает n своим следующим ходом.

Рассмотрим такое число l, что l больше, чем n/2, и позиция l является проигрышной. В зависимости от четности числа n/2, l равно либо n/2 + 1, либо n/2 + 2. Теперь рассмотрим все числа от l/2 до n/2 включительно. Все эти позиции будут выигрышными, поскольку если удвоить любое из этих чисел, получится число, большее n/2 и четное, а такая позиция проигрышна. Получили два отрезка, на первом из которых выигрышна каждая позиция, а на втором — каждая вторая.

Заметим, что остальные отрезки можно получить, вызвав F(l/2 - 1). Разбором случаев можно показать, что l/2 - 1 всегда равно n/4, округленному вниз. Убедимся в том, что требуемое свойство выполняется. Пусть x l/2 - 1. Тогда 2x l - 2 n/2, то есть все позиции, большие l/2 - 1, и в которые возможен ход из позиции, не большей l/2 - 1 являются выигрышными, и потому такой ход приведет к проигрышу.

При каждом рекурсивном вызове n уменьшается как минимум в 4 раза, поэтому программа работает за O(logn). После этого решить изначальную задачу становится просто. Так как все эти отрезки не пересекаются, можно пройтись по ним в возрастающем порядке и определять, попадает ли ответ в текущий отрезок. Если текущее k больше количества чисел на данном отрезке, то вычтем это количество из k и перейдем к следующему отрезку. Иначе мы можем получить k нужное нам число на этом отрезке и вывести его. Если такого отрезка не нашлось, следует вывести -1.