Автор задачі: | Фейса Богдан |
Задачу підготував: | Фейса Богдан |
Розбір написав: | Павло Ціцей |
Визначити чи існує послідовність операцій можна так: якщо не ділиться на 2^k то відповідь , так як не існує послідовності. Інакше завжди можна створити таке число. Як мінімум можна це зробити за \frac{x}{2^k} операцій кожен раз використовуючи другу кнопку.
Щоб знайти послідовність цих операцій можна використати такий жадібний алгоритм. Нехай ми вже використали першу кнопку разів та має бітів. Тоді щоб визначити чи ми маємо спочатку додати 2^k чи потрібно далі використати першу кнопку, потрібно перевірити n-q-тий біт числа . Якщо він рівний 1, то перед операцією потрібно додати 2^k. Ці дії потрібно повторювати поки не отримаємо число .