2014-05-12

UVa 1636 - Headshot

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

You have a revolver gun with a cylinder that has n chambers. Chambers are located in a circle on a cylinder. Each chamber can be empty or can contain a round. One chamber is aligned with the gun’s barrel. When trigger of the gun is pulled, the gun’s cylinder rotates, aligning the next chamber with the barrel, hammer strikes the round, making a shot by firing a bullet through the barrel. If the chamber is empty when the hammer strikes it, then there is no shot but just a click.

You have found a use for this gun. You are playing Russian Roulette with your friend. Your friend loads rounds into some chambers, randomly rotates the cylinder, aligning a random chamber with a gun’s barrel, puts the gun to his head and pulls the trigger. You hear click and nothing else – the chamber was empty and the gun did not shoot.

Now it is your turn to put the gun to your head and pull the trigger. You have a choice. You can either pull the trigger right away or you can randomly rotate the gun’s cylinder and then pull the trigger. What should you choose to maximize the chances of your survival?

Input

The input file contains several datasets. A dataset contains a single line with a string of n digits 0 and 1 ( 2 <= n <= 100). This line of digits represents the pattern of rounds that were loaded into the gun’s chambers. 0 represent an empty chamber, 1 represent a loaded one. In this representation, when cylinder rotates before a shot, the next chamber to the right gets aligned with the barrel for a shot. Since the chambers are actually located on a circle, the first chamber in this string follows the last one. There is at least one 0 in this string.

Output

For each dataset, write to the output file one of the following words (without quotes):

SHOOT – if pulling the trigger right away makes you less likely to be actually shot in the head with the bullet (more likely that the chamber will be empty).
ROTATE – if randomly rotating the cylinder before pulling the trigger makes you less likely to be actually shot in the head with the bullet (more likely that the chamber will be empty).
EQUAL – if both of the above choices are equal in terms of probability of being shot.

Sample Input

1
2
3

0011
0111
000111

Sample Output

1
2
3

EQUAL
ROTATE
SHOOT

Solution

題目描述：

俄羅斯輪盤，現在與一位朋友一起玩這場遊戲，然而我們已經知道左輪手槍中的填彈資訊，剛聽到朋友按下扣板，但是沒有死。現在輪到你，請問要直接按？還是隨機轉一圈再按？

題目解法：

不外乎地，我們要找到哪個機率高。

由於朋友按下沒死，也就是要考慮連續 2 個 0 的情況，下一個是 0 的機率為 czero / zero

// 在前提為 0 的情況下，下一個為 0 的機率為何，也就是考慮 00 和 01 的情況下，00 的機率為何。
// czero 是連續為 0 的個數，zero 是 0 的個數 (同時也是 00 01 的個數。)，n 是全部個數。

隨機轉一圈得到 0 的概率為 zero / n。

不小心把題目想太難，事實上這問題很簡單的。

#include <stdio.h>
#include <string.h>
int main(){
    char s[1024];
    while(scanf("%s", s) == 1){
        int n = strlen(s);
        int zero = 0, one = 0, czero = 0;
        for(int i = 0 ; i < n ; i++ ){
            if(s[i] == '1') 
                continue;
            zero++;
            if(s[(i+1)%n] == '0') czero++;
        }
        // czero - zero * (zero / n)
        if(czero * n == zero * zero) 
            puts("EQUAL");
        else if(czero * n > zero * zero)
            puts("SHOOT");
        else 
            puts("ROTATE");
    }
    return 0;
}

Morris' Blog