Автор задачі: | Ціцей Павло |
Задачу підготував: | Ціцей Павло, Фейса Богдан |
Розбір написав: | Ціцей Павло |
Помітимо, що якщо число n\le 2^k, то \sqrt{n}\le 2^{k/2}. Це означає, що достатньо зробити log_2(k) разів операцію корінь, щоб став рівним 1. Іншими словами, нехай це таке число, що 2^a\ge k. Тоді, ми можемо зробити максимум операцій з умови, щоб перетворити в . При наших обмеженнях, a\le 6, так як k\le 64.
Через те, що у нас завжди буде вибір або заокруглити вниз, або вверх, у нас всього буде 2 варіанти для кожного числа, отже якщо ми запустимо повний перебір, то переберемо максимум 2^a=k варіантів.