记录编号	604768	评测结果	AAAAAAAAAA
题目名称	3451.Power Calculus	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	3.620 s
提交时间	2025-08-11 18:40:08	内存使用	3.65 MiB

#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
int a[40],n,k,flag;
bool dfs(int x,int sum){
	if(x==k+1)return sum==n;
	if(sum*(1<<(k-x+1))<n)return 0;
	a[x]=sum;
	for(int i=1;i<=x;i++){
		if(dfs(x+1,sum-a[i])||dfs(x+1,sum+a[i]))return 1;
	}
	return 0;
}
void work(){
	for(int i=0;;i++){
		k=i;
		if(dfs(1,1))break;
	} 
	cout<<k<<endl;
	return;
}
int main(){
	freopen("pow_cal.in","r",stdin);
	freopen("pow_cal.out","w",stdout);
	while(cin>>n&&n)work();
	return 0;
}