记录编号	604773	评测结果	AAAAAAAAAA
题目名称	3451.Power Calculus	最终得分	100
用户昵称	pcx	是否通过	通过
代码语言	C++	运行时间	4.351 s
提交时间	2025-08-11 19:21:34	内存使用	3.66 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,s,a[222],ans[1111];
bool dfs(int s,int p){
    if(s>m||p<=0||(p<<(m-s))<n) return 0;
    if(p==n) return 1;
    a[s]=p;
    for(int i=0;i<=s;i++){
        if(dfs(s+1,p+a[i])) return 1;
        if(dfs(s+1,p-a[i])) return 1;
    }
    return 0;
}
int main(){
    freopen("pow_cal.in","r",stdin);
    freopen("pow_cal.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>n){
        if(!n) break;
        if(ans[n]){
            cout<<ans[n]<<endl;
            continue;
        }
        m=0;a[0]=1;
        for(;1;m++){
            if(dfs(0,1)){
                ans[n]=m;
                cout<<m<<endl;
                break;
            }
        }
    }
    return 0;
}