Informatica Online Judge

  힘 미적분학 [2268 / 08DC]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 3   Total Tried : 3


The Champion of this Problem (C++) : gs16103 - ms / 1119byte
My Best Submission (C++) : N/A

[Asi Regional Contest 2006]

Background

원준이는 미적분학을 잘 못한다. 왜냐하면 미적분학을 하는 데 있어서 기초적인 요소인 계산 능력이 딸리기 때문이다! 계산을 많이 할수록 실수를 안 할 확률이 기하급수적으로 감소하기 때문에 원준이는 계산의 횟수를 최소화하려고 한다.

어떤 수 x가 주어졌을 때, x의 n제곱을 구하는 문제가 있다. n이 31일 때를 생각하자.

일일이 곱한다면, 30번의 곱셈을 해야 한다.

$$x^2 = x × x, x^3 = x^2 × x, x^4 = x^3 × x, …, x^{31} = x^{30} × x.$$

거듭제곱을 사용할 수 있다면, 8번의 곱셈만으로 가능하다.

$$x^2 = x × x, x^3 = x^2 × x, x^6 = x^3 × x^3, x^7 = x^6 × x, x^{14} = x^7 × x^7, x^{15} = x^{14} × x, x^{30} = x^{15} × x^{15}, x^{31} = x^{30} × x.$$

이미 구했던 값을 종이에 적어 놓았다가 다시 사용하는 방법을 이용하면, 7번만의 연산으로 31제곱을 구할 수 있다.

$$x^2 = x × x, x^4 = x^2 × x^2, x^8 = x^4 × x^4, x^8 = x^4 × x^4, x^{10} = x^8 × x^2, x^{20} = x^{10} × x^{10}, x^{30} = x^{20} × x^{10}, x^{31} = x^{30} × x.$$

나눗셈을 하는 데도 곱셈과 똑같은 확률로 실수를 한다면, 나눗셈을 사용하여 6번 만에 구할 수 있다.

$$x^2 = x × x, x^4 = x^2 × x^2, x^8 = x^4 × x^4, x^{16} = x^8 × x^8, x^{32} = x^{16} × x^{16}, x^{31} = x^{32} ÷ x.$$

위 방법이 x의 31제곱을 구하는 가장 연산을 적게 사용하는 방법이다.

원준이의 미적분학 성적을 위하여 가장 적은 횟수의 연산(곱셈 또는 나눗셈)을 사용하는 방법을 알려 주자!

단, 원준이는 분수 계산을 잘 못하기 때문에 중간 과정에서 음수인 지수가 나오면 안 된다. 즉, $x^{-3}$가 나오면 안 된다.

Input

하나 이상의 줄에, 각 줄 마다 하나의 정수 n이 들어온다$(1<=n<=1000)$. 입력은 0이 들어옴으로써 종료된다. 0이 아닌 입력의 개수는 1000을 넘지 않는다.

Output

각각의 n에 대하여, 한 줄에 하나씩 $x^n$을 만드는 데 필요한 최소 연산 횟수를 출력한다.

IO Example

예제 입력

1
31
70
91
473
512
811
953
0

예제 출력

0
6
8
9
11
9
13
12

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]