记录编号	604749	评测结果	AAAAAAAAAA
题目名称	3451.Power Calculus	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	5.648 s
提交时间	2025-08-11 17:32:01	内存使用	3.83 MiB

#include<bits/stdc++.h>
using namespace std;

int num[100001],n,dep;

bool dfs(int step,int now){
    if(now<=0||step>dep||now<<(dep-step)<n) return 0;
    if(now<<(dep-now)==n) return 1;
    if(now==n) return 1;
    num[step]=now;
    for(int i=0;i<=step;i++){
        if(dfs(step+1,now+num[i])) return 1;
        if(dfs(step+1,now-num[i])) return 1;
    }
    return 0;
}

int main(){
//	freopen("in.in","r",stdin);
	freopen("pow_cal.in","r",stdin);
	freopen("pow_cal.out","w",stdout);
    while(1){
        scanf("%d",&n);
        if(n==0) break;
        for(dep=0;;dep++){
            if(dfs(0,1)) break;
        }
        printf("%d",dep);
    }
    return 0;
}