
ZOJ Problem Set  2824
Starting with x and repeatedly multiplying by x, we can compute x^{31} with thirty multiplications:
The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute x^{31} with eight multiplications:
This is not the shortest sequence of multiplications to compute x^{31}. There are many ways with only seven multiplications. The following is one of them:
If division is also available, we can find a even shorter sequence of operations. It is possible to compute x^{31} with six operations (five multiplications and one division):
This is one of the most efficient ways to compute x^{31} if a division is as fast as a multiplication. Your mission is to write a program to find the least number of operations to compute x^{n} by multiplication and division starting with x for the given positive integer n. Products and quotients appearing in the sequence should be x to a positive integer��s power. In others words, x^{−3}, for example, should never appear. Input The input is a sequence of one or more lines each containing a single integer n. n is positive and less than or equal to 1000. The end of the input is indicated by a zero. Output Your program should print the least total number of multiplications and divisions required to compute x^{n} starting with x for the integer n. The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces. Sample Input 1 31 70 91 473 512 811 953 0 Sample Output 0 6 8 9 11 9 13 12 Source: Asia Regional Contest, Yokohama, 2006 