Zero Sum
DESCRIPTION
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
A single line with the integer N (3 <= N <= 9).
7
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
THOUGHTS:
注意n<=9,对于如此小的数据范围,我们第一反应便是暴力(DFS),复杂度3^n,完全可以通过。 所以这道题非常简单,只需要Dfs到最后判定一下是否式子的结果为0即可。 至于字典序输出,我们观察样例,可以发现’ ’ < ‘+’ < ‘-‘,那么只需要分别让012代表’ ‘, ‘+’, ‘-‘即可。
DIFFICULTIES: pj-
AC PROGRAM:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (register int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define ROF(i, a, b) for (register int i = (a), i##_end_ = (b); i > i##_end_; --i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const char Fin[] =
"zerosum.in";
const char Fout[] =
"zerosum.out";
void In()
{
freopen(Fin,
"r", stdin);
freopen(Fout,
"w", stdout);
return ;
}
const int MAXN =
15;
int n;
int A[MAXN];
int B[MAXN];
void Print()
{
FOR(i,
1, n)
{
printf(
"%d", i);
switch (A[i])
{
case 0:
printf(
" ");
break;
case 1:
printf(
"+");
break;
default:
printf(
"-");
}
}
printf(
"%d\n", n);
return ;
}
void Check()
{
int last(
1), num(
0), ans(
0);
memset(B,
0,
sizeof B);
A[n] =
1;
FOR(i,
1, n +
1)
{
B[num] = B[num] *
10 + i;
if(A[i])
{
if(last ==
2)
B[num] = -B[num];
last = A[i];
++num;
}
}
FOR(i,
0, num)
ans += B[i];
if(!ans)
Print();
return ;
}
void Dfs(
int cur)
{
if(cur == n)
Check();
else
{
FOR(i,
0,
3)
{
A[cur] = i;
Dfs(cur +
1);
}
}
return ;
}
int main()
{
In();
scanf(
"%d", &n);
Dfs(
1);
return 0;
}
Skq_Liao 2017/07/11 9:40 于 AB213