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) |
|
| | | | 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) |
|
| | | | Returns: 2 | | The ball does not change spots when 0 swaps are performed; therefore, the ball must be at spot 2. | | |
| 2) |
|
| | |
| 3) |
|
| | |
| 4) |
|
| | |
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%。給出初始狀態，總共有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;
}
};