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

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數(shù)據(jù)加載中……

            SRM549 DIVⅡ 250pt (概率想法題)

            Problem Statement

                 A magician has invited you to play a game. For this game, the magician uses a special table. On the table there are three spots in a row. The spots are labeled 0, 1, and 2, in order. He places three hats onto the table, so that each hat covers one of the spots. He then takes a ball and places it under one of the hats. The hats are not transparent, so you cannot see the ball while it is under a hat. Next, the magician shuffles the hats by repeatedly swapping two adjacent hats. Each swap is done by sliding the hats along the table, never showing you the ball. Once the magician finishes swapping the hats, you have to guess the spot where the ball is.

            You are given a string hats which describes the contents of the hats in the beginning of the game. The i-th character of hats is 'o' if the ball was initially on the spot i. Otherwise, the i-th character of hats is '.' (a period).

            You are also given a int numSwaps. Assume that the magician swapped the hat that contained the ball exactly numSwaps times. Please remember that in our version of the game the magician always swaps two adjacent hats. Also, note that the total number of swaps in the game may be larger than numSwaps, because the magician may sometimes swap two hats that don't contain the ball.

            Assume that the magician chose the swaps he makes uniformly at random. That is, in each turn with probability 50% he swapped the hats on spots 0 and 1, and with probability 50% he swapped the hats on spots 1 and 2. Return the number of the spot that is most likely to contain the ball at the end of the game. If multiple spots are tied for the largest probability, return the smallest one of them.

            Definition

                
            Class: BallAndHats
            Method: getHat
            Parameters: string, int
            Returns: int
            Method signature: int getHat(string hats, int numSwaps)
            (be sure your method is public)
                

            Notes

            - Two hats are adjacent if their spots differ by 1.

            Constraints

            - hats will contain exactly three characters.
            - hats will contain exactly one 'o' character.
            - hats will contain exactly two '.' characters.
            - numSwaps will be between 0 and 1000, inclusive.

            Examples

            0)
                
            ".o."
            1
            Returns: 0
            The spots 0 and 2 are equally likely to contain the ball after the hat that contains it is swapped once. We return the smallest spot number, which is 0.
            1)
                
            "..o"
            0
            Returns: 2
            The ball does not change spots when 0 swaps are performed; therefore, the ball must be at spot 2.
            2)
                
            "o.."
            1
            Returns: 1

            3)
                
            "..o"
            2
            Returns: 0

            4)
                
            "o.."
            101
            Returns: 1

            This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.




            題意:給三個帽子,一個帽子下面有氣球。一次SWAP可將相鄰的兩個帽子交換。每次SWAP的概率一樣的,0和1,1和2交換的概率都是50%。給出初始狀態(tài),總共有numSwaps次SWAP了帶氣球的帽子。問最后氣球在哪個位置的概率最大,如果有幾個位置,則求最小的位置。

            思路:想法題!numSwaps奇偶性討論分析

            176.5pt  thinking速度太低,多分析分析,鍛煉思維哦!
            #include<string>
            using namespace std;
            class BallAndHats{
            public:
                
            int getHat(string hats, int numSwaps){
                    
            int i=0;
                    
            while (hats[i]!='o')    i++;
                    
            if (numSwaps==0)
                        
            return i;
                    numSwaps
            %=2;
                    
            if (i==0 && numSwaps==0)
                        
            return 0;
                    
            if (i==1 && numSwaps==1)
                        
            return 0;
                    
            if (i==2 && numSwaps==0)
                        
            return 0;
                    
            return 1;
                }
            };




            posted on 2012-07-10 09:03 wangs 閱讀(222) 評論(0)  編輯 收藏 引用 所屬分類: Topcoder

            狠狠色丁香久久婷婷综合五月 | 日韩中文久久| 久久久久亚洲爆乳少妇无 | 99久久中文字幕| 久久久精品视频免费观看| 中文字幕久久亚洲一区| 久久丫精品国产亚洲av| 久久久国产精品| 狠狠色丁香久久婷婷综| 久久婷婷五月综合国产尤物app| 国产精品欧美久久久天天影视| 欧美精品一区二区久久| 国产一级做a爰片久久毛片| 久久久噜噜噜久久中文字幕色伊伊| 久久精品9988| 久久久久亚洲精品无码蜜桃| 欧美日韩精品久久久久| 日本久久久久久中文字幕| 亚洲精品无码久久久久去q| 久久精品国产精品亚洲| 精品国产一区二区三区久久| 性欧美大战久久久久久久久| 久久国产成人亚洲精品影院| 国产成人久久精品区一区二区| 99久久夜色精品国产网站| 日韩人妻无码一区二区三区久久99| 99久久精品免费看国产免费| 97久久久精品综合88久久| 日韩人妻无码精品久久免费一| 久久免费视频1| 久久人妻AV中文字幕| 波多野结衣AV无码久久一区| 亚洲精品WWW久久久久久| 久久久久久久免费视频| 香蕉久久久久久狠狠色| 久久午夜福利无码1000合集| 人妻无码精品久久亚瑟影视 | 97精品伊人久久大香线蕉app| 久久综合88熟人妻| 狠狠色丁香婷婷久久综合不卡| …久久精品99久久香蕉国产|