Codeforces Round 774 (Div. 2) |
---|
Закончено |
Число называется сильным, если оно является степенью двойки или факториалом. Другими словами, число $$$m$$$ сильное, если существует неотрицательное целое число $$$d$$$ такое, что $$$m=2^d$$$ или $$$m=d!$$$, где $$$d!=1\cdot 2\cdot \ldots \cdot d$$$ (в частности, $$$0! = 1$$$). Например, $$$1$$$, $$$4$$$ и $$$6$$$ являются сильными, потому что $$$1=1!$$$, $$$4=2^2$$$, $$$6=3!$$$, а $$$7$$$, $$$10$$$ или $$$18$$$ не являются.
Вам дано положительное число $$$n$$$. Найдите минимальное число $$$k$$$ такое, что $$$n$$$ можно представить в виде суммы $$$k$$$ различных сильных чисел, или определите, что такого $$$k$$$ не существует.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Описание одного набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 10^{12}$$$).
Для каждого набора входных данных выведите ответ на отдельной строке.
Если $$$n$$$ не может быть представлено как сумма различных сильных чисел, выведите $$$-1$$$.
Иначе выведите одно положительное число — минимально возможное число $$$k$$$.
471124017179869184
2 3 4 1
В первом примере $$$7$$$ может быть представлена как $$$7=1+6$$$, где $$$1$$$ и $$$6$$$ являются сильными. Так как $$$7$$$ не является сильным числом, мы знаем, что минимальное значение $$$k$$$ в этом случае $$$k=2$$$.
Во втором примере один из способов разложить $$$11$$$ в сумму трех сильных чисел такой: $$$11=1+4+6$$$. Можно показать, что нельзя представить $$$11$$$ в виде суммы двух или менее сильных чисел.
В третьем примере $$$240$$$ может быть представлено как $$$240=24+32+64+120$$$. Обратите внимание, что $$$240=120+120$$$ не является корректным представлением, т. к. сильные числа должны быть различны.
В четвертом примере $$$17179869184=2^{34}$$$, поэтому $$$17179869184$$$ является сильным числом, и минимальное $$$k$$$ в этом случае $$$k=1$$$.
Название |
---|