USACO 2.3 Zero Sum 零的算式和

Zero Sum

Consider the sequence of digits from 1 through N (where N=9) in increasing order: 1 2 3 ... N.

Now insert either a `+' for addition or a `-' for subtraction or a ` ' [blank] to run the digits together between each pair of digits (not in front of the first digit). Calculate the result that of the expression and see if you get zero.

Write a program that will find all sequences of length N that produce a zero sum.

PROGRAM NAME: zerosum
INPUT FORMAT
A single line with the integer N (3 <= N <= 9).
SAMPLE INPUT (file zerosum.in)
7

OUTPUT FORMAT
In ASCII order, show each sequence that can create 0 sum with a `+', `-', or ` ' between each pair of numbers.
SAMPLE OUTPUT (file zerosum.out)
1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7


USACO_2.3-3:zerosum零的算式和

Time Limit:1000MS  Memory Limit:65536K
Total Submit:6 Accepted:4

Description

请考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。现在请在数列中插入“+”表示加，或者“-”表示减，抑或是“ ”表示空白，来将每一对数字组合在一起（请不在第一个数字前插入符号）。计算该表达式的结果并注意你是否得到了和为零。请你写一个程序找出所有产生和为零的长度为N的数列。

Input

PROGRAM NAME: zerosum

单独的一行表示整数N (3 <= N <= 9)。


Output

按照ASCII码的顺序，输出所有在每对数字间插入“+”, “-”, 或 “ ”后能得到和为零的数列。

Sample Input


7

Sample Output


1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

========================= 华丽的分割线 =========================
　　一个DFS, 题目说了按ASCII的顺序进行输出, 也就是先' ', 再'+', 接着'-'.., 我拿到题目就写了一个程序,, DFS没写错, 就是算和的时候错了. 试着写了几个版本, 都错了..(看样子我还是不怎么滴啊~~ 狂汗'').
　　不说多的废话了, 代码贴上来:

/*
LANG: C
ID: zqy11001
PROG: zerosum
*/
#include <stdio.h>
#define getint(i) scanf("%d", &i)
#define putint(i) printf("%d", i)
#define ze(now, c) str[now] = c; zero(now + 1);
#define MAX 200

int n;
char str[9];

void out(void)
{
	int i;
	putchar('1');
	for(i = 1; i < n; i++){
		printf("%c%d", str[i], i + 1);
	}
	putchar('\n');
}

void zero(int sum, int t, int now, char s)
{
	if(now == n){
		if(s == '+'){
			sum += t;
		}else{
			sum -= t;
		}
		if(sum == 0 && str[0] == '+'){
			out();
		}
		return;
	}
	str[now] = ' ';
	zero(sum, t * 10 + now + 1, now + 1, s);
	if(s == '+'){
		sum += t;
	}else{
		sum -= t;
	}
	str[now] = '+';
	zero(sum, now + 1, now + 1, '+');
	str[now] = '-';
	zero(sum, now + 1, now + 1, '-');
}

int main(void)
{
	int i, j;
	freopen("zerosum.in", "r", stdin);
	freopen("zerosum.out", "w", stdout);
	getint(n);
	zero(0, 0, 0, '+');
	return 0;
}