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

            為生存而奔跑

               :: 首頁 :: 聯系 :: 聚合  :: 管理
              271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

            留言簿(5)

            我參與的團隊

            搜索

            •  

            積分與排名

            • 積分 - 328415
            • 排名 - 74

            最新評論

            閱讀排行榜

            評論排行榜

            SRM 144 DIV1 550

            Problem Statement

                

            In most states, gamblers can choose from a wide variety of different lottery games. The rules of a lottery are defined by two integers (choices and blanks) and two boolean variables (sorted and unique). choices represents the highest valid number that you may use on your lottery ticket. (All integers between 1 and choices, inclusive, are valid and can appear on your ticket.) blanks represents the number of spots on your ticket where numbers can be written.

            The sorted and unique variables indicate restrictions on the tickets you can create. If sorted is set to true, then the numbers on your ticket must be written in non-descending order. If sorted is set to false, then the numbers may be written in any order. Likewise, if unique is set to true, then each number you write on your ticket must be distinct. If unique is set to false, then repeats are allowed.

            Here are some example lottery tickets, where choices = 15 and blanks = 4:

            • {3, 7, 12, 14} -- this ticket is unconditionally valid.
            • {13, 4, 1, 9} -- because the numbers are not in nondescending order, this ticket is valid only if sorted = false.
            • {8, 8, 8, 15} -- because there are repeated numbers, this ticket is valid only if unique = false.
            • {11, 6, 2, 6} -- this ticket is valid only if sorted = false and unique = false.

            Given a list of lotteries and their corresponding rules, return a list of lottery names sorted by how easy they are to win. The probability that you will win a lottery is equal to (1 / (number of valid lottery tickets for that game)). The easiest lottery to win should appear at the front of the list. Ties should be broken alphabetically (see example 1).

            Definition

                
            Class: Lottery
            Method: sortByOdds
            Parameters: vector <string>
            Returns: vector <string>
            Method signature: vector <string> sortByOdds(vector <string> rules)
            (be sure your method is public)
                

            Constraints

            - rules will contain between 0 and 50 elements, inclusive.
            - Each element of rules will contain between 11 and 50 characters, inclusive.
            - Each element of rules will be in the format "<NAME>:_<CHOICES>_<BLANKS>_<SORTED>_<UNIQUE>" (quotes for clarity). The underscore character represents exactly one space. The string will have no leading or trailing spaces.
            - <NAME> will contain between 1 and 40 characters, inclusive, and will consist of only uppercase letters ('A'-'Z') and spaces (' '), with no leading or trailing spaces.
            - <CHOICES> will be an integer between 10 and 100, inclusive, with no leading zeroes.
            - <BLANKS> will be an integer between 1 and 8, inclusive, with no leading zeroes.
            - <SORTED> will be either 'T' (true) or 'F' (false).
            - <UNIQUE> will be either 'T' (true) or 'F' (false).
            - No two elements in rules will have the same name.

            主要是運用了排列組合的知識,其中,最難的是,從n個數中找出m個數,要求這m個數必須是排好序的,并且可以重復,可以把它轉化為從n+m-1個數中選出m個數,且是排好序的,答案就是C(n+m-1,m)
            // BEGIN CUT HERE

            // END CUT HERE
            #line 5 "Lottery.cpp"
            #include 
            <algorithm>
            #include 
            <vector>
            #include 
            <string>
            #include 
            <iostream>
            #include 
            <math.h>
            #include 
            <sstream>
            using namespace std;
            typedef 
            long long int64;
            class TICKET
            {
            public:
                
            string name;
                int64 rate;
            }
            ;
            bool operator < (const TICKET & t1,const TICKET & t2)
            {
                
            if(t1.rate!=t2.rate)
                    
            return t1.rate<t2.rate;
                
            else return t1.name<t2.name;
            }

            vector
            <TICKET>tickets;
            class Lottery
            {
            private:
                
            int choices,blanks;    
                
            bool sorted,unique;

            public:
                vector 
            <string> sortByOdds(vector <string> rules)
                
            {
                    vector
            <string>::iterator it;
                    
            for(it=rules.begin();it!=rules.end();it++)
                    
            {
                        TICKET ticket;
                        ticket.name
            =split(*it);
                        ticket.rate
            =process();
                        tickets.push_back(ticket);
                    }

                    sort(tickets.begin(),tickets.end());
                    vector
            <string> ans;
                    
            for(vector<TICKET>::iterator it=tickets.begin();it!=tickets.end();it++)
                        ans.push_back(it
            ->name);
                    
            return ans;
                }


                
            string split(string rule)
                
            {
                    
            string::size_type pos,pos2;
                    pos 
            = rule.find_first_of(':');
                    
            string name=rule.substr(0,pos);

                    
            char ch1,ch2;
                    istringstream ist(rule.substr(pos
            +2,rule.size()));
                    ist
            >>choices>>blanks>>ch1>>ch2;
                    sorted
            =(ch1=='T'?1:0);
                    unique
            =(ch2=='T'?1:0);
                    
            //pos+=2; //去掉一個空格

                    
            //pos2 = rule.find_first_of(' ',pos);
                    
            //choices=0;
                    
            //for(string::size_type i=pos;i<pos2;i++)
                    
            //    choices=choices*10+(rule[i]-'0');
                    
            //
                    
            //pos2++;
                    
            //blanks=rule[pos2]-'0';

                    
            //pos2+=2;
                    
            //sorted = (rule[pos2]=='T'?1:0);

                    
            //pos2+=2;
                    
            //unique = (rule[pos2]=='T'?1:0);

                    
            return name;
                }


                int64 process()
                
            {
                    
            if(sorted && unique)
                        
            return C(choices,blanks);
                    
            else if(!sorted && !unique)
                        
            return pow((double)choices,blanks);
                    
            else if(!sorted && unique)
                        
            return A(choices,blanks);
                    
            else
                    
            {
                        
            return C(choices-1+blanks,blanks);
                    }

                }


                int64 A(
            int m,int n)
                
            {
                    int64 res
            =1;
                    
            for(int i=m;i>=m-n+1;i--)
                        res
            *=i;
                    
            return res;
                }


                int64 C(
            int m,int n)
                
            {
                    
            //return A(m,n)/A(n,n);
                    int64 res=1;
                    
            for(int i=m;i>=m-n+1;i--)
                        res
            *=i;
                    
            for(int i=2;i<=n;i++)
                        res
            /=i;
                    
            return res;
                }

            }
            ;
            // BEGIN CUT HERE
            int main()
            {
                Lottery test;
                
            string Arr0[] = {"INDIGO: 93 8 T F",
                                 
            "ORANGE: 29 8 F T",
                                 
            "VIOLET: 76 6 F F",
                                 
            "BLUE: 100 8 T T",
                                 
            "RED: 99 8 T T",
                                 
            "GREEN: 78 6 F T",
                                 
            "YELLOW: 75 6 F F"}
            ;
                vector 
            <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); 
                vector
            <string> ans = test.sortByOdds(Arg0);
                
            for(vector<string>::iterator it=ans.begin();it!=ans.end();it++)
                cout
            <<*it<<endl;
                
            return 0;
            }

            // END CUT HERE

            posted on 2009-08-13 12:41 baby-fly 閱讀(558) 評論(0)  編輯 收藏 引用 所屬分類: TopCoder
            久久香蕉国产线看观看乱码| 伊人久久成人成综合网222| 久久久久亚洲Av无码专| 一本久道久久综合狠狠爱| 久久人人妻人人爽人人爽| 国内精品人妻无码久久久影院| 国产成人精品白浆久久69| 婷婷综合久久狠狠色99h| 日本WV一本一道久久香蕉| 国内精品久久国产大陆| 中文字幕无码av激情不卡久久| 99久久无色码中文字幕人妻| 日本免费久久久久久久网站| 大香伊人久久精品一区二区| 51久久夜色精品国产| 久久综合给久久狠狠97色| 久久久久国色AV免费看图片| 91久久婷婷国产综合精品青草| 亚洲综合久久夜AV | 久久久久亚洲爆乳少妇无 | 久久久青草青青亚洲国产免观| 久久久久人妻一区二区三区 | 性做久久久久久久久| 精品久久久久久国产免费了| 97久久综合精品久久久综合| 国内精品久久久久影院一蜜桃| 狠狠色狠狠色综合久久| 久久午夜无码鲁丝片秋霞| 国产精品久久久久a影院| 久久久久久久91精品免费观看 | 一个色综合久久| 亚洲国产精品无码久久久蜜芽| 亚洲国产精品无码久久一线| 久久精品天天中文字幕人妻| 久久亚洲私人国产精品vA| 99久久无码一区人妻a黑| 精品久久久久久久久久久久久久久| 国内精品九九久久久精品| 国产成人无码精品久久久免费| 国产三级精品久久| 精品综合久久久久久97|