• <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

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            伊人久久大香线焦AV综合影院 | 色婷婷综合久久久中文字幕| 久久综合久久综合亚洲| 国产成人无码精品久久久性色| 亚洲中文精品久久久久久不卡| 无码人妻久久一区二区三区免费| 国产美女久久精品香蕉69| 99久久99久久精品免费看蜜桃| 国产99久久久国产精免费| 亚洲欧美另类日本久久国产真实乱对白 | 久久久无码精品亚洲日韩蜜臀浪潮| 欧美精品一本久久男人的天堂| 久久影院久久香蕉国产线看观看| 无码人妻久久一区二区三区| 国产女人aaa级久久久级| 久久精品国产亚洲AV蜜臀色欲| 久久99精品国产麻豆宅宅| 亚洲精品99久久久久中文字幕| 99久久人妻无码精品系列蜜桃| 香蕉aa三级久久毛片| 色综合合久久天天综合绕视看| 国产精品久久久久久久app| AV色综合久久天堂AV色综合在| 久久只这里是精品66| 99热成人精品免费久久| 久久99久久99精品免视看动漫| 日韩欧美亚洲综合久久 | 国产精品久久新婚兰兰| 久久丝袜精品中文字幕| AV无码久久久久不卡蜜桃| 99蜜桃臀久久久欧美精品网站| 久久最新免费视频| 国产亚洲成人久久| 精品免费久久久久国产一区| 久久91精品国产91久久小草 | 精品久久久久国产免费| 久久91精品国产91久久户| 久久被窝电影亚洲爽爽爽| 久久久久久狠狠丁香| 色综合久久中文综合网| 久久亚洲国产午夜精品理论片|