记录编号	571935	评测结果	AAAAAAAAAA
题目名称	幂次计算	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	2.110 s
提交时间	2022-06-26 14:52:21	内存使用	17.37 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=5000000;
int n;
int a[N],d=0;
int abs(int x){
    if (x>=0)return x;
    return -x;
}
bool dfs(int num,int now){
    if ((num<<(d-now))<n)return 0;
    if (now>d)return 0;
    if (num==n)return 1;
    a[now]=num;
    for (int i=0;i<=now;i++){
        if (dfs(num+a[i],now+1)==1||dfs(abs(num-a[i]),now+1)==1){
            return 1;
        }
    }
    return 0;
}
int main(){
    freopen ("mico.in","r",stdin);
    freopen ("mico.out","w",stdout);
    while(scanf("%d",&n)!=EOF){
        if (n==0)return 0;
        d=0;
        while(dfs(1,0)==0){
            d++;
        }
        printf("%d\n",d);
    }
    return 0;
}