Codeforces Round 739 (Div. 3) |
---|
Закончено |
Дано число $$$n$$$. За $$$1$$$ ход можно сделать одно из следующих действий:
Действия можно производить в любом порядке произвольное количество раз.
Обратите внимание, что если после удаления некоторой цифры из числа оно будет содержать ведущие нули, то они не будут удаляться автоматически. Например, если из числа $$$301$$$ удалить $$$3$$$, то останется $$$01$$$, а не $$$1$$$.
Необходимо совершить минимальное количество действий, так чтобы число стало степенью $$$2$$$ (т. е. чтобы нашлось целое число $$$k$$$ ($$$k \ge 0$$$) такое, что полученное число равно $$$2^k$$$). Полученное число не должно содержать ведущих нулей.
Например, если $$$n=1052$$$, то ответ равен $$$2$$$. Сначала можно дописать справа цифру $$$4$$$ (получится $$$10524$$$). Затем стереть цифру $$$5$$$, в результате получится $$$1024$$$, что является степенью числа $$$2$$$.
Например, если $$$n=8888$$$, то ответ равен $$$3$$$. Три раза сотрём любую из цифр $$$8$$$. В результате получится $$$8$$$, что является степенью числа $$$2$$$.
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.
Каждый набор входных данных состоит из одной строки, содержащей одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$).
Для каждого набора входных данных в отдельной строке выведите целое число $$$m$$$ — минимальное количество ходов, которые нужно совершить, чтобы число стало степенью $$$2$$$.
12 1052 8888 6 75 128 1 301 12048 1504 6656 1000000000 687194767
2 3 1 3 0 0 2 1 3 4 9 2
Ответ на первый набор входных данных разобран выше.
Ответ на второй набор входных данных разобран выше.
В третьем наборе входных данных достаточно приписать справа цифру $$$4$$$ — число $$$6$$$ превратится в $$$64$$$.
В четвёртом наборе входных данных можно сначала приписать справа $$$8$$$, затем удалить $$$7$$$ и $$$5$$$ — получится число $$$8$$$.
В пятом и шестом наборах входных данных числа уже являются степенями двойки, поэтому ни одного хода делать не нужно.
В седьмом наборе данных можно сначала удалить цифру $$$3$$$ (останется $$$01$$$), затем удалить цифру $$$0$$$ (получится $$$1$$$).
Название |
---|