Домашній улюбленець Сакурако#388

Домашній улюбленець Сакурако (Розбір)

Автор задачі:

Ціцей Павло

Задачу підготував:

Ціцей Павло, Фейса Богдан

Розбір написав:

Ціцей Павло

Помітимо, що якщо число 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 варіантів.