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

            SRM459

            Posted on 2010-01-20 19:24 rikisand 閱讀(347) 評論(0)  編輯 收藏 引用 所屬分類: TopcoderAlgorithm

            幾次沒寫了,這兩天給補上~~

            晚上果然不清醒,250的就卡了很久,然后直接看1000,算概率的,有個樣例沒看明白,其實早上一下就想明白了···500的十分鐘基本寫對了,沒來得及交~ 倆字 杯具~~

            250pt

            Problem Statement

            Draw a square with side length sideLength on a plane. Then, inscribe a circle in the square. Inscribe another square in that circle, and yet another circle in the second square. Continue this process until K circles appear on the plane.
            For example, if K=3, the picture would look like this:

            For each circle, compute the area within the circle that does not belong to any other figure inside that circle. Return the sum of those areas. In the example above, the area to compute is colored in stripes.

            Definition

            Class:
            RecursiveFigures

            Method:
            getArea

            Parameters:
            int, int

            Returns:
            double

            Method signature:
            double getArea(int sideLength, int K)

            (be sure your method is public)

            Notes

            -
            Your return value must have an absolute or relative error less than 1e-9.

            -
            The area of square with side length A is A*A.

            -
            The area of circle with radius R is pi*R*R.

            -
            The length of diameter of the circle inscribed in a square is equal to the square's side length.

            -
            The side length of the square inscribed in circle with radius R is equal to R*sqrt(2).

            Constraints

            -
            sideLength will be between 1 and 100, inclusive.

            -
            K will be between 1 and 10, inclusive.

            Examples

            0)

            10
            1
            Returns: 78.53981633974483

            1)

            10
            2
            Returns: 67.80972450961724

            2)

            10
            3
            Returns: 62.444678594553444

                    double getArea(int side, int K)
                    {
                        double ans = 0.;int n=side;double r=side;
                        for(int i=0;i<K;i++){
                            ans += r*r*(1-acos(-1.)/4.); //正方形面積減去圓面積
                            r /= pow(2.,0.5);
                        }
                        return n*n - ans;
                    }

             

            500pt

            You are given six integers, minx, maxx, miny, maxy, minz and maxz. Return the number of triplets of integers (x,y,z) that satisfy the following three conditions:

            • x is between minx and maxx, inclusive.
            • y is between miny and maxy, inclusive.
            • z is between minz and maxz, inclusive.
            • x * y = z
            Definition

            Class:
            ProductTriplet

            Method:
            countTriplets

            Parameters:
            int, int, int, int, int, int

            Returns:
            long long

            Method signature:
            long long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz)

            (be sure your method is public)

            Constraints

            -
            maxx will be between 1 and 1,000,000,000, inclusive.

            -
            maxy will be between 1 and 1,000,000,000, inclusive.

            -
            maxz will be between 1 and 1,000,000,000, inclusive.

            -
            minx will be between 1 and maxx, inclusive.

            -
            miny will be between 1 and maxy, inclusive.

            -
            minz will be between 1 and maxz, inclusive.

            Examples

            0)

            2
            2
            3
            3
            6
            6
            Returns: 1

            2 * 3 = 6.

            1)

            2
            2
            3
            3
            7
            7
            Returns: 0

            2 * 3 is not 7.

            2)

            6
            8
            4
            5
            27
            35
            Returns: 4

            (x,y,z) = (6,5,30), (7,4,28), (7,5,35) and (8,4,32) satisfy all conditions.

            3)

            1
            458
            1
            458
            1
            458
            Returns: 2877

            4)

            8176
            184561
            1348
            43168
            45814517
            957843164
            Returns: 2365846085
                    int maximumSubset(vector <string> in)
                    {
                         vector<int> vec(2010,0); 
                         int mx=0;
                         for(int j=0;j<in.size();j++){
                            stringstream ss(in[j]);string str1,str;int s;
                            ss>>str1>>str>>s;double k=-1;
                            for(int i=0;i<2008;i++){
                                k+=0.5;
                                bool tag=false;
                                if(str=="="){
                                    if(s==k)tag=true;
                                }
                                else if(str==">="){
                                    if(k>=s)tag=true;
                                }
                                else if(str==">"){
                                    if(k>s)tag=true;
                                }
                                else if(str=="<="){
                                    if(k<=s)tag=true;
                                }
                                else if(str=="<"){
                                    if(k<s)tag=true;
                                } 
                                if(tag)vec[i]++;
                            }
                         }
                            for(int i=0;i<2008;i++)if(vec[i]>mx)mx=vec[i];
                         //for(int i=0;i<2008;i++){
                            //k+=0.5;
                            //for(int j=0;j<in.size();j++){
                            //    stringstream ss(in[j]);string str1,str;int s;
                            //    ss>>str1>>str>>s;
                            //    bool tag=false;
                            //    if(str=="="){
                            //        if(s==k)tag=true;
                            //    }
                            //    else if(str==">="){
                            //        if(k>=s)tag=true;
                            //    }
                            //    else if(str==">"){
                            //        if(k>s)tag=true;
                            //    }
                            //    else if(str=="<="){
                            //        if(k<=s)tag=true;
                            //    }
                            //    else if(str=="<"){
                            //        if(k<s)tag=true;
                            //    } 
                            //    if(tag)vec[i]++;
                            //}
                            //if(vec[i]>mx)mx=vec[i];
                         //}
                         return mx;
                    }

            要計算最多能滿足的不等式,其實只需要枚舉所有0到1000的數(shù)看看每一個能滿足的最多不等式數(shù)量,由于k可以是小數(shù),所以以步長0.5遞增即可

            1000pt

            A new ride is opened in an amusement park. It consists of N landings numbered from 0 to N-1. Some of the landings are connected with pipes. All of the landings are at different heights, so the pipes are all inclined and can only be traversed downwards.
            A ride-taker begins his ride at some landing. The pipes are long enough that he cannot see where they lead before entering them. Therefore, at each landing, any descending pipe adjacent to it has an equal probability of being used by a ride-taker who reached this landing.
            A ride is finished when a ride-taker reaches a landing which has no adjacent descending pipes. There are two types of such landings: exits and crocodile ponds. If the ride-taker reaches the exit landing, his ride is over and he safely returns home. If one reaches the crocodile pond, his trip is also over, but he never returns home.
            You're given a vector <string> landings describing the ride. Element i of landings describes the i-th landing. If the landing is an exit, the i-th character of landings[i] will be 'E' and the rest of the characters will be '0's (zeroes). If it is a crocodile pond, the i-th character will be 'P' and the rest will be '0's. If the landing has at least one adjacent descending pipe, the j-th character of landings[i] will be '1' (one) if a pipe descends from the i-th landing to the j-th, and '0' (zero) otherwise.
            A ride-taker began his ride at a randomly chosen landing, used a total of K pipes throughout his descent and safely returned home afterwards. Each of the landings has the same probability of being chosen as the initial landing of the ride. Compute the probability that he started the ride at landingstartLanding.

            Definition

            Class:
            ParkAmusement

            Method:
            getProbability

            Parameters:
            vector <string>, int, int

            Returns:
            double

            Method signature:
            double getProbability(vector <string> landings, int startLanding, int K)

            (be sure your method is public)

            Notes

            -
            Your return value must have an absolute or relative error less than 1e-9.

            Constraints

            -
            landings will contain exactly N elements, where N is between 2 and 50, inclusive.

            -
            Each element of landings will contain exactly N characters.

            -
            Each character in landings will be '0' (zero), '1' (one), 'E', or 'P'.

            -
            If the i-th element of landings contains an 'E', it will contain only one 'E' as its i-th character, and all other characters in that element will be '0'.

            -
            If the i-th element of landings contains a 'P', it will contain only one 'P' as its i-th character, and all other characters in that element will be '0'.

            -
            If the i-th element of landings doesn't contain an 'E' or a 'P', it will contain at least one '1' character. The i-th character of such element will always be '0'.

            -
            K will be between 1 and N-1, inclusive.

            -
            startLanding will be between 0 and N-1, inclusive.

            -
            There will be no cycles in landings, i.e. it's never possible to return to the same landing after descending through several pipes.

            -
            There will be at least one landing from which it is possible to reach an exit using exactly K pipes.

            Examples

            0)

            {"E000",
             "1000",
             "1000",
             "1000"}
            1
            1
            Returns: 0.3333333333333333

            The ride contains 4 landings, one of which is an exit. Each of the other landings has a single pipe descending to the exit landing. Therefore, each of them could be the starting landing with equal probability of 1/3.

            1)

            {"E000",
             "1000",
             "1001",
             "000P"}
            1
            1
            Returns: 0.6666666666666666

            This time, there is an exit landing and a crocodile pond. Of the other two landings, the first has a descending pipe only to the exit, while the second is connected both to the exit and to the pond. So, the probability of reaching an exit starting from landing 2 is lower and the chances of ground 1 being the start of the journey increase.

            2)

            {"01000100",
             "00111000",
             "00001010",
             "000E0000",
             "0000E000",
             "00000P00",
             "000000P0",
             "01000000"}
            1
            2
            Returns: 0.14285714285714288

            Analyzing the graph above, we can see that landings 0, 1 and 7 could be the starting landings. One can reach an exit from landing 0 using 2 pipes with probability 2/6, from landing 1 with probability 1/6 and from landing 7 with probability 2/3. Therefore, the probability that the ride-taker began from landing 1 is equal to (1/6)/(2/3+2/6+1/6)=1/7.

            3)

            {"0100",
             "0010",
             "0001",
             "000E"}
            0
            2
            Returns: 0.0

            Obviously, the only way to get to the exit landing using 2 pipes is from ground 1. Therefore there is no chance that landing 0 was the initial ground.

            4)

            {"E00",
             "0E0",
             "010"}
            0
            1
            Returns: 0.0

            Note that some sections of the ride might be disconnected.

            #define REP(i, n) for (int i = 0; i < (n); ++i)  
            double dp[55][55];
            vector<string> A ; int N;
            int mp[55];
            double cacl(int now,int steps){
                if(dp[now][steps]!=-1)return dp[now][steps];
                double& t = dp[now][steps];
                t=0.;int cnt=0;
                REP(i,N){
                    if(A[now][i]=='1'){
                        cnt++;t+=cacl(i,steps-1);
                    }
                }
                t /= cnt;
                return t;
            }
            class ParkAmusement
            {
                    public:
                    double getProbability(vector <string> land, int start, int K)
                    {
                        A=land;      N=land.size();
                        REP(i,N+1)REP(j,N+1)dp[i][j]=-1;
                        memset(mp,0,sizeof(mp));// 0 
                        REP(i,N) 
                            REP(j,N){
                                if(A[i][j]=='E'){
                                    mp[i]=1;
                                    REP(k,N+1)dp[i][k]=0.;
                                    dp[i][0]=1.;
                                }
                                else if(A[i][j]=='P')
                                {
                                    mp[i]=2;
                                    REP(k,N+1)dp[i][k]=0.;
                                }
                            } 
                        for(int i=0;i<N;i++) 
                            cacl(i,K); 
                        double ans=0.;
                        REP(i,N)ans+=dp[i][K];
                        return dp[start][K]/ans;
                    }

            要求從某個出發(fā)安全完成的概率,應(yīng)該等于從這里出發(fā)安全完成的概率比上從各個點出發(fā)安全完成概率和。因此要求從每一個點出發(fā)安全到達的概率。由于計算中可能出現(xiàn)重復(fù)計算,因此使用備忘錄memo[i][j] 計算從i出發(fā)經(jīng)過j步驟安全到達的概率,而此點概率即為此點到其各個鄰接點的安全概率和除以鄰接點個數(shù),所以很簡單,一遍就ac了,可惜晚上沒想明白~

             

             

            99久久久精品免费观看国产| 久久国产免费直播| 久久无码精品一区二区三区| www性久久久com| 久久Av无码精品人妻系列 | 久久久无码精品亚洲日韩蜜臀浪潮| 国产精品免费看久久久| 久久精品国产亚洲精品2020| 久久婷婷五月综合色高清| 久久精品a亚洲国产v高清不卡| 久久综合给合久久狠狠狠97色 | A级毛片无码久久精品免费| 四虎国产精品成人免费久久| 狠狠色婷婷久久综合频道日韩| 久久久久久久久波多野高潮| 色偷偷偷久久伊人大杳蕉| 999久久久无码国产精品| 91久久精品国产91性色也| 免费一级欧美大片久久网| 狠狠色综合网站久久久久久久高清| 综合久久国产九一剧情麻豆| 久久99国内精品自在现线| 日本精品久久久中文字幕| 亚洲欧洲久久av| 久久精品国产清高在天天线| 999久久久免费国产精品播放| 亚洲国产精品成人久久蜜臀| 久久久久久亚洲精品成人| 久久本道久久综合伊人| 久久久无码精品亚洲日韩蜜臀浪潮 | 日韩美女18网站久久精品 | 亚洲精品tv久久久久久久久| 久久精品免费观看| 欧美精品国产综合久久| a级毛片无码兔费真人久久| 久久婷婷五月综合成人D啪| 亚洲国产成人久久综合一 | 亚洲精品午夜国产va久久| 久久久久人妻一区精品色| 欧美久久久久久午夜精品| 97久久精品国产精品青草|