Олимпиады для начинающих: Московская олимпиада, 6 класс, 2021 год

Стёпа — простой парень из мегаполиса, который только начал заниматься программированием. Прочитав рекомендации на никому неизвестном сайте в далёком уголке интернета, он решил начать изучение тем с прочтения разборов недавно прошедших олимпиад. Простые задачи показались ему совсем не интересными, его внимание привлекла неизвестная ему ранее структура под названием «дерево отрезков», и он решил плотно заняться её изучением.

Через пару дней он встретился со своим более опытным другом Вацлавом, который решил проверить его знания и дал ему следующую задачу.

Даны три числа \(a\), \(b\), \(k\). Найти два числа \(x\) и \(y\) (\(y \leq x\)), состоящие из \(a\) нулей и \(b\) единиц в двоичной системе счисления каждое, причём такие, что \(x - y\) в двоичной системе содержит в себе ровно \(k\) единиц. В \(x\) и \(y\) ведущие нули запрещены.

Напомним, что двоичная система счисления устроена аналогично десятичной. А именно, в данном случае число \(2\) — это основание системы счисления, любое неотрицательное целое число может быть записано цифрами со значениями \(0\) или \(1\). В такой записи, если у числа длина \(k\), и число имеет запись вида \(\overline{a_{k-1}a_{k-2}a_{k-3} \ldots a_1a_0}\), то величина числа равна \(a_0 + a_1 \cdot 2^1 + a_2 \cdot 2^2 + a_3 \cdot 2^3 + \ldots + a_{k-1} \cdot 2^{k - 1}\). При этом, если у числа длина больше 1, то старшая цифра не должна равняться 0, то есть, если \(k > 1\), то \(a_{k-1} > 0\). Но если длина равна 1, то число может состоять из единственной цифры \(0\).

Например, число \(20\) можно записать в двоичной системе счисления как \(20 = 10100_{2}\).

Стёпа все еще не верит, что такую задачу можно решить без использования продвинутых структур данных. Помогите ему решить её во что бы то ни стало!