USACO Section 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

Analysis

This problem is a very simple DFS problem. Thanks to the little limitation, we are easy to search all of the situations because we only need to search 3^8=6561 situations. So,just search.

Code


/**//*
ID:braytay1
PROG:zerosum
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ofstream fout("zerosum.out");
ifstream fin("zerosum.in");
string oper[3]={" ","+","-"};
string equt;
int N;
int cal(string s){
    string tmp;
    for(int i=0;i<s.size();i++){
        if (s[i]!=' ') {tmp.push_back(s[i]);}
    }
    int ls=1,sum=0;
    char op=' ';
    for (int i=1;i<tmp.size();i++){
        if (tmp[i]>='1'&&tmp[i]<='9') {
            ls=10*ls+(tmp[i]-48);
        }
        else {
            if (op=='+') {sum+=ls;op=tmp[i];ls=0;continue;}
            if (op=='-') {sum-=ls;op=tmp[i];ls=0;continue;}
            else{sum+=ls;op=tmp[i];ls=0;}
        }
    }
    switch (op){
    case '+':sum+=ls;break;
    case '-':sum-=ls;break;
    default: sum=-1;
    }    
    return sum;
}
void DFS(int step){
    if (step>N-1){
        if (cal(equt)==0) {fout<<equt<<endl;return;}
        else return;
    }
    for (int i=0;i<3;i++){
        equt+=oper[i];
        equt.push_back(step+1+48);
        DFS(step+1);
        equt.erase(equt.end()-2,equt.end());
    }
}
int main(){
    fin>>N;
    equt+="1";
    DFS(1);
    return 0;
}

posted on 2008-08-12 00:45 幻浪天空領主 閱讀(224) 評論(0)  編輯 收藏 引用 所屬分類: USACO