USACO 2.3.3 – Zero Sum

#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <sstream>
char sign[4] = "-+ ";
using namespace std;

int main() {
	int N;
	freopen("zerosum.in", "r", stdin), freopen("zerosum.out", "w", stdout);
	scanf("%d", &N);
	stack<vector<int> > st; st.push(vector<int>());
	while (st.size()) {
		vector<int> s = st.top();
		st.pop();
		if (int(s.size()) < N - 1){
			for (int i = 0; i < 3; i++) {
				vector<int> t = s; t.push_back(i); st.push(t);
			}
			continue;
		}
		int n = 1, sum = 0;
		stringstream line;
		line << 1;
		for (int i = 0; i < int(s.size()); i++) {
			if (s[i] == 2)  n = n * 10 +  (n > 0 ? 1 : -1)*(i+2);
			if (s[i] == 1)  sum += n, n = i + 2;
			if (s[i] == 0)  sum += n, n = -i - 2;
			line << sign[s[i]] << int(i + 2);
		}
		if (sum + n == 0)
			puts(line.str().c_str());
	}
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: