• <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 閱讀(348) 評論(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的數看看每一個能滿足的最多不等式數量,由于k可以是小數,所以以步長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;
                    }

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

             

             

            午夜精品久久久久久影视riav| 2020久久精品亚洲热综合一本| 久久综合久久美利坚合众国| 亚洲欧美另类日本久久国产真实乱对白 | 国产免费久久精品99re丫y| 欧美粉嫩小泬久久久久久久 | 国产一久久香蕉国产线看观看| 久久久久综合网久久| 亚洲国产日韩欧美综合久久| 久久国产乱子伦免费精品| 久久国产精品偷99| 精品综合久久久久久888蜜芽| 狠狠综合久久综合中文88 | 亚洲精品午夜国产VA久久成人| 久久精品九九亚洲精品| 亚洲国产日韩欧美久久| 一本大道久久a久久精品综合| 2021国产精品久久精品| 久久国产视频99电影| 91精品国产9l久久久久| 久久久亚洲裙底偷窥综合| 国产成人香蕉久久久久| 国产成人久久精品激情| 香蕉久久夜色精品国产尤物| 久久久精品国产亚洲成人满18免费网站 | 久久国产精品国语对白| 久久精品国产一区| 99久久人妻无码精品系列蜜桃| 久久精品极品盛宴观看| 久久夜色撩人精品国产| 国内精品久久久久国产盗摄| 天天久久狠狠色综合| 久久国产精品久久久| 久久精品aⅴ无码中文字字幕重口| 免费精品久久天干天干| 一级A毛片免费观看久久精品| 久久久久久A亚洲欧洲AV冫| 99久久精品国产毛片| 99久久www免费人成精品| 久久天天躁狠狠躁夜夜2020| 久久精品中文字幕第23页|