牛客网 NC17866 谁是神射手

目录

• 牛客网 NC17866 谁是神射手
  • 目录
  • 1. 题目描述
    • 1.1. Title
    • 1.2. Time Limit
    • 1.3. Memory Limit
    • 1.4. Problem Description
    • 1.5. Input
    • 1.6. Output
    • 1.7. Sample Input 1
    • 1.8. Sample Output 1
    • 1.7. Sample Input 2
    • 1.8. Sample Output 2
    • 1.10. Source
  • 2. 题解
  • 3. 代码

1. 题目描述

1.1. Title

牛客网 NC17866 谁是神射手

1.2. Time Limit

C/C++ 1秒，其他语言2秒

1.3. Memory Limit

C/C++ 32768K，其他语言65536K

1.4. Problem Description

有一天，MWH突然来了兴致，想和CSL比比谁枪法好。于是他们找来了一个瓶子，比比看谁先打中这个瓶子。 给定MWH的命中率 $\alpha\%$ 和CSL的命中率 $\beta\%$。 两人轮流射击，MWH先手，问谁获胜的概率大？

1.5. Input

输入两个整数 $\alpha$ 和 $\beta$，表示MWH和CSL的命中率。$(0 \leq \alpha,\beta \leq 100)$.

1.6. Output

若MWH获胜的概率大，则输出"MWH"。 若CSL获胜的概率大，则输出"CSL"，否则输出"equal"。

1.7. Sample Input 1

100 100

1.8. Sample Output 1

MWH

1.7. Sample Input 2

0 100

1.8. Sample Output 2

CSL

1.10. Source

牛客网 NC17866 谁是神射手

2. 题解

轮次	先手赢的概率	后手赢的概率
1	$\alpha$	$(1-\alpha)\beta$
2	$(1-\alpha)(1 - \beta)\alpha$	$(1-\alpha)^2(1 - \beta)\beta$
3	$(1-\alpha)^2(1 - \beta)^2\alpha$	$(1-\alpha)^3(1 - \beta)^2\beta$

先手赢的概率为

$$P(A) = \sum_{n = 0}^{\infty} (1-\alpha)^n(1 - \beta)^n \alpha$$

后手赢的概率为

$$P(B) = \sum_{n = 0}^{\infty} (1-\alpha)^{n + 1}(1 - \beta)^n\beta$$

可以转化为等比数列求和问题

$$S_n=a_1+a_1q+a_1q^2+...+a_1q^{n-1}$$

$$qS_n=a_1q+a_1q^2+a_1q^3+...+a_1q^{n}$$

两式相减

$$(1-q)S_n = a_1-a_1q^n$$

得到求和公式

$$S_n = \frac{a_1(1 - q^{n})}{1-q}$$

求极限得

$$\lim\limits_{x \to \infin}{S_n} = \frac{a_1}{1-q}$$

带入$P(A)$和 $P(B)$。

$$P(A) = \frac{\alpha}{1-(1-\alpha)(1 - \beta)}$$

$$P(B) = \frac{(1 - \alpha) \beta}{1-(1-\alpha)(1 - \beta)}$$

分母是一样的，所以只比较分子 $\alpha$ 和 $(1 - \alpha) \beta$ 的大小就可以了。

3. 代码

#include <iostream>
using namespace std;

int main()
{
    int x, y;
    cin >> x >> y;
    int rateX = x;
    int rateY = y * (100 - x) / 100;
    if (rateX == rateY) {
        cout << "equal" << endl;
    } else if (rateX > rateY) {
        cout << "MWH" << endl;
    } else {
        cout << "CSL" << endl;
    }
    //
}

---

联系邮箱：curren_wong@163.com

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。