桂花游戏

【来源：牛客网 “菜鸟杯”华中师范大学程序设计新生赛（同步赛）】

链接：https://ac.nowcoder.com/acm/contest/26134/J

（略有改动）

题目描述

华中师范大学坐落于美丽的桂子山上。每年的秋天，华师校园内都洋溢着袭人心怀，沁人肺腑的桂花芳香。

小哈和小赫都是华师智商最高的学生，小哈了解到小赫十分喜欢桂花，便想摘一些送给她，但是小哈比较内向，不敢直接表达自己的心意，他便想用一个游戏来送一些桂花给小赫。

小哈邀请小赫来参加了这个桂花游戏，小哈给小赫介绍了游戏规则：

在每轮中，他们都可以向对方展示一个数，该数可为 $0$ 或者 $1$

当他们展示的数不同时，小赫会获得 $X$ 朵桂花

当他们展示的数都是 $1$ 时，小哈会获得 $Y$ 朵桂花

当他们展示的数都是 $0$ 时，小哈会获得 $Z$ 朵桂花

他们会玩这个桂花游戏 $2^{100000}$ 轮，小赫十分喜欢这个游戏，她会在游戏中想办法赢下更多的桂花。为了让小赫有一个更好的游戏体验，小哈也会想办法赢下更多的桂花。请你判断一下最后谁可以获得更多的桂花呢？

输入描述

第一行为一个整数 $T$ ，代表输入数据的组数。接下来的 $T$ 行每行包括三个整数 $X, Y, Z$ 三者由空格隔开。

$T \leq 500 T ≤500$
$1 \leq X, Y, Z \leq 10 1≤X,Y,Z ≤10$
$Y + Z \leq 2 X Y+Z≤2X$

输出描述

如果小哈获得的桂花更多，就输出"xiaoha"，如果小赫获得的桂花更多，就输出"xiaohe"，如果是平局，就输出"ping"。

样例

输入

4 2 1

1 1 1

输出

xiaohe

ping

题目分析

观察样例，及题面中的 $X+Y {\leq} 2Z$ 猜测当 $Y + Z = 2 X$ 时，平局。当 $Y + Z < 2 X$ 时，小赫获胜。故伪代码为

if Y+Z=2X:
    print("ping")
else:
	print("xiaohe")

提交后发现 WA 了。

进一步观察，猜测当 $X = Y = Z$ 时，平局。否则，小赫获胜。故伪代码为

if X=Y=Z:
    print("ping")
else:
	print("xiaohe")

提交，愉快 AC 。

但是，以上解答均只是猜测，如何严格证明呢？

证明

将小赫得到 $m$ 朵桂花记为 $+ m$ ，小哈得到 $m$ 朵桂花记为 $- m$ ，则若最后桂花数为正，则小赫赢，桂花数为 $0$ 则平局，桂花数为负则小哈赢。设小赫出 $1$ 的概率为 $p_{1}$ ，小哈出 $1$ 的概率为 $p_{2}$ ，则可以列出如下表格

	$p_{1}$	$1 - p_{1}$
$p_{2}$	$- Y$	$+ X$
$1 - p_{2}$	$+ X$	$- Z$

每次游戏桂花数的期望

$E = X p_{1} (1 - p_{2}) + X p_{2} (1 - p_{1}) - Y p_{1} p_{2} - Z (1 - p_{1}) (1 - p_{2})$

即 $E = - (2 X + Y + Z) p_{1} p_{2} + (X + Z) p_{1} + (X + Z) p_{2} - Z$

若小赫获胜，则 $\exists p_1\in[0,1],\forall p_2\in[0,1],E>0$

计算可知 $\frac{Z}{X+Z}<p_1<\frac{X}{X+Y}$

若 $X + Y < 2 Z$ ，则 $0<\frac{Z}{X+Z}<\frac{X}{X+Y}<1$

因此，只要小赫将出 $1$ 的概率控制在区间 $(\frac{Z}{X+Z},\frac{X}{X+Y})$ 内，经过 $2^{100000}$ 后即可获胜。

AC代码(C++)

#include<iostream>
using namespace std;
int T,X,Y,Z;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&X,&Y,&Z);
        if(X==Y&&Y==Z)puts("ping");
        else puts("xiaohe");
    }
    return 0;
}

时间复杂度为 $O (T)$