Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Power Calculus
Description Starting with
The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute
This is not the shortest sequence of multiplications to compute
If division is also available, we can find a even shorter sequence of operations. It is possible to compute
This is one of the most efficient ways to compute Your mission is to write a program to find the least number of operations to compute 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 Output Your program should print the least total number of multiplications and divisions required to compute 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 |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator