• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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

            <2011年6月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            狠狠色伊人久久精品综合网| 久久久久久免费一区二区三区 | 亚洲精品乱码久久久久久蜜桃不卡 | 久久精品无码一区二区三区| 久久中文骚妇内射| 91精品国产综合久久香蕉| 91久久精品国产91性色也| 伊人 久久 精品| 青青国产成人久久91网| 亚洲人成网站999久久久综合| 久久不见久久见免费视频7| 伊人久久综在合线亚洲2019 | 亚洲精品成人网久久久久久| 色偷偷偷久久伊人大杳蕉| 国产精品va久久久久久久| 亚洲国产精品无码久久98| 91精品国产高清久久久久久国产嫩草 | 国产精品欧美久久久天天影视 | 久久久久99精品成人片直播| 久久亚洲中文字幕精品一区四 | 久久综合综合久久综合| 国产亚洲精午夜久久久久久| 四虎国产精品成人免费久久| 青青青国产成人久久111网站| 亚洲欧美日韩中文久久| 精品久久久久久国产免费了| 久久超乳爆乳中文字幕| 午夜天堂精品久久久久| 99精品国产综合久久久久五月天| 精品久久人人爽天天玩人人妻| 国产精品一区二区久久| 精品久久久噜噜噜久久久 | 国产一区二区三区久久精品| 午夜不卡久久精品无码免费| 国内高清久久久久久| 久久人人爽人人爽人人片AV不| 伊人久久大香线蕉无码麻豆| 久久久精品久久久久影院| 亚洲欧美国产日韩综合久久| 亚洲乱码日产精品a级毛片久久| 久久久久亚洲AV成人网|