首页 > ACM题库 > HDU-杭电 > HDU 3910-Liang Guo Sha-概率-[解题报告]HOJ
2015
04-14

HDU 3910-Liang Guo Sha-概率-[解题报告]HOJ

Liang Guo Sha

问题描述 :

Maybe you know “San Guo Sha”, but I guess you didn’t hear the game: “Liang Guo Sha”!

Let me introduce this game to you. Unlike “San Guo Sha” with its complicated rules, “Liang Guo Sha” is a simple game, it consists only four cards, two cards named “Sha”, and the other named “Shan”.

Alice and Bob are good friends, and they’re playing “Liang Guo Sha” now. Everyone has two cards: a “Sha” and a “Shan”. Each round, everyone choose a card of his/her own, and show it together(Just show the selected card, do not need to put it away). If both of them choose “Sha”, then Alice gets A points, and Bob loses A points; if both of them choose “Shan”, then Alice gets B points, and Bob loses B points; otherwise, Bob gets C points, and Alice loses C points.  

Both Alice and Bob wants to get points as many as possible, they thought a optimal strategy: Calculating a percentage of choosing card “Sha” in order to ensure that even the opponent uses the optimal strategy, he/she can still get a highest point exceptation.
  
Here is the question, if both Alice and Bob use the optimal strategy to make their points higher, what is the expectation point which Alice can get in a round?

输入:

Several test case, process to EOF.
  Each test case has only a line, consists three positive integers: A, B, C respectively.
  1 <= A, B, C <= 100000

输出:

Several test case, process to EOF.
  Each test case has only a line, consists three positive integers: A, B, C respectively.
  1 <= A, B, C <= 100000

样例输入:

2 10 4
3 3 3

样例输出:

0.200000
0.000000
Hint
In test case 1, both Alice and Bob calculated the best percentage of choosing “Sha”, and the their percentage are the same: 70%. If Bob do not choose the best percentage, his strategy might be targetd. For example, if Bob choose 100%, then Alice can change her percentage to 100%, Bob might lose many points. Bob is clever, so he won’t do that.

数学期望

题意:使Alice和Bob两个人拿到杀的概率互相不受影响。

分析:假设Alice拿到杀的概率是x,Bob拿到杀的概率是y,则Alice的期望是

E(x) = x*y*A + (1-x)*(1-y)*B – (1-x)*y*C – x*(1-y)*C

        = (1-x)*B – x*C + [x*A - (1-x)*B - (1-x)*C + x*C]*y

令y的系数为0,解得x = (B+C)/(A+B+2*C) , 所以E(x) = (1-x)*B – x*C

AC代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>

int main() {
	int a, b, c;
	while(scanf("%d%d%d", &a, &b, &c)!=EOF) {
		double x = (double)(b + c) / (a + b + 2 * c);
		printf("%.6lf\n", (1 - x) * b - c * x);
	}	
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/chuck_0430/article/details/14548521


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  4. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。