Антон купує кабанчика

Автор задачі: | Фейса Богдан
Задачу підготував: | Фейса Богдан
Розбір написав: | Павло Ціцей

Визначити чи існує послідовність операцій можна так: якщо $$$x$$$ не ділиться на $$$2^k$$$ то відповідь $$$-1$$$, так як не існує послідовності. Інакше завжди можна створити таке число. Як мінімум можна це зробити за $$$\frac{x}{2^k}$$$ операцій кожен раз використовуючи другу кнопку.

Щоб знайти послідовність цих операцій можна використати такий жадібний алгоритм. Нехай ми вже використали першу кнопку $$$q$$$ разів та $$$x$$$ має $$$n$$$ бітів. Тоді щоб визначити чи ми маємо спочатку додати $$$2^k$$$ чи потрібно далі використати першу кнопку, потрібно перевірити $$$n-q$$$-тий біт числа $$$x$$$. Якщо він рівний 1, то перед операцією потрібно додати $$$2^k$$$. Ці дії потрібно повторювати поки не отримаємо число $$$x$$$.