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

#include <bits/stdc++.h>
using namespace std;
int n,ans;
int a[1008];
bool dfs(int k,int num,int dep){
	if(k>dep||num<0||num*(1<<dep-k)<n) return 0;		
	if(num==n||num*(1<<dep-k)==n){
		return 1;
	}
	a[k]=num;
	for(int i=0;i<=k;i++){
		if(dfs(k+1,num+a[i],dep)){
			return 1;
		}
		if(dfs(k+1,num-a[i],dep)){
			return 1;
		}
	}
	return 0;
}
int main(){		
	while(cin>>n){
		if(n==0){
			break;
		}
        if(n==1){
            cout<<0<<"\n";
            continue;
        }
		a[0]=1;
		int dep=0;
		while(!dfs(0,1,dep)){
			dep++;
		}				
		cout<<dep<<"\n"; 
	} 

	return 0;
}