记录编号	571956	评测结果	AAAAAAAAAA
题目名称	幂次计算	最终得分	100
用户昵称	ZRQ	是否通过	通过
代码语言	C++	运行时间	1.755 s
提交时间	2022-06-26 16:22:44	内存使用	4.59 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=500050;
int n,c[N],dep;
bool DFS(int nw,int st)
{
    if(st>dep) return 0;
    if(nw<<(dep-st)<n) return 0;
    if(nw==n) return 1;
    c[st]=nw;
    for(int i=0;i<=st;++i)
    {
        if(DFS(nw+c[i],st+1)) return 1; 
        if(DFS(abs(nw-c[i]),st+1)) return 1;
    }
    return 0;
}
int main()
{
    freopen("mico.in","r",stdin);
    freopen("mico.out","w",stdout);
    while(scanf("%d",&n))
    {
        if(!n) break;
        dep=0;
        while(!DFS(1,0)) ++dep;
        printf("%d\n",dep);
    }
    return 0;
}