• <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 幻浪天空領主 閱讀(225) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            97久久国产综合精品女不卡| 久久精品aⅴ无码中文字字幕不卡| 久久综合九色综合欧美就去吻| 四虎国产精品免费久久5151 | 91精品国产色综久久| 美女写真久久影院| 亚洲AV伊人久久青青草原| 伊人久久无码中文字幕| 久久99免费视频| 久久久久久精品成人免费图片| 日韩精品久久无码中文字幕| 婷婷久久综合九色综合98| 亚洲人成无码www久久久| 久久亚洲高清观看| 伊人色综合久久天天网| 久久99精品国产麻豆宅宅| 久久强奷乱码老熟女网站| 精品乱码久久久久久久| 亚洲va久久久噜噜噜久久| 久久国产精品久久久| 久久无码国产专区精品| 亚洲国产成人久久综合一| 日韩人妻无码一区二区三区久久99| 久久久国产精品网站| 国内精品伊人久久久久777| 国产A级毛片久久久精品毛片| 久久精品中文騷妇女内射| 日韩十八禁一区二区久久| 国产精品岛国久久久久| 久久久无码精品亚洲日韩按摩| 中文成人久久久久影院免费观看| 国产成人综合久久精品尤物| 精品久久香蕉国产线看观看亚洲| 中文字幕久久久久人妻| 国产精品中文久久久久久久| 久久久久综合中文字幕| 久久精品国产一区二区三区| 久久国产成人午夜AV影院| 九九久久精品无码专区| 久久久久亚洲?V成人无码| 久久乐国产精品亚洲综合|