UVA 1374: Power Calculus

1374-ac.cpp

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

#define fori(i,s,e) for(int i = s; i < ((int)e); i++)
#define allof(s) (s).begin(), (s).end()

const int MAX = 3000;
bool seen[MAX];
bool skipped[MAX];
vector<int> stack;

// depth = how many more operations we have
bool dfs(int depth, int target) {
	// fprintf(stderr, "[...%d: %d]\n", depth, stack.back());
	if (depth == 1) {
		// we must use the most recent number because otherwise there's no point
		// for (int s : stack) { fprintf(stderr, "[%d]", s); }
		int recent = stack.back();
		if (recent + target < MAX && seen[recent + target]) return true;
		if (target - recent > 0 && seen[target - recent]) return true;
		return false;
	}

	if ((*max_element(allof(stack)) << depth) < target) return false;

	set<int> candidates;
	for (size_t i = 0; i < stack.size(); i++) {
		for (size_t j = i; j < stack.size(); j++) {
			for (int sign = 1; sign >= -1; sign -= 2) {
				int combination = abs(stack[i] + sign * stack[j]);
				if (combination == 0) continue;

				if (combination >= target * 2) continue;

				if (seen[combination]) continue;
				if (skipped[combination]) continue;

				candidates.insert(combination);
			}
		}
	}

	for (const int & cand : candidates) {
		stack.push_back(cand);
		seen[cand] = true;
		if (dfs(depth - 1, target)) return true;
		seen[cand] = false;
		stack.pop_back();
		skipped[cand] = true;
	}
	for (const int & cand : candidates) {
		skipped[cand] = false;
	}
	return false;
}

int solve(int target) {
	if (target == 1) return 0;

	stack.clear();
	fill(seen, seen + 3000, false);
	fill(skipped, skipped + 3000, false);
	stack.push_back(1);
	seen[1] = true;

	for (int depth = 1; ; depth++) {
		if (dfs(depth, target)) return depth;
	}
}

int main() {
	int x;
	while (cin >> x, x) {
		cout << solve(x) << "\n";
	}
}