跳至正文

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;
}

发表回复

您的电子邮箱地址不会被公开。