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

#include <bits/stdc++.h>

int n, mx;
int a[1010];

bool dfs(int x, int t) {
    if (x << (mx - t) < n) return false;
    if (t > mx) return false;
    if (x == n) return true; 
    a[t] = x;
    for (int i = 0; i <= t; ++ i) {
        if (dfs(x + a[i], t + 1))           return true;
        if (dfs(std::abs(x - a[i]), t + 1)) return true;
    }
    return false;
}

int main() {
    freopen("mico.in", "r", stdin); 
    freopen("mico.out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    while (std::cin >> n, n) {
        #define clear memset(a, 0, sizeof a)
        clear, mx = 0;
        while (clear, !dfs(1, 0)) ++ mx;
        std::cout << mx << '\n';
    }
    return 0;
}