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;
}
};