[ACM_HDU_1410]PK武林盟主

杰拉斯 | 时间：2012-04-20, Fri | 21,262 views
编程算法　

PK武林盟主

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 621 Accepted Submission(s): 133

Description

枫之羽认为自己很强，想当武林盟主，于是找现任武林盟主氢氧化铜挑战。氢氧化铜欣然接受了挑战，两人约好于下个月的月圆之夜在HDU校园内的三根柱子上进行决战。这场PK赛肯定能吸引武林中所有人前来观战，所以他们找了有商业运作潜力的经济人你，让你来组织这场百年一见的世纪之战，假设两人都有一定的血HP1、HP2.HP1是枫之羽的，HP2是氢氧化铜的。他们也有一定攻击力AP1、AP2，AP1是枫之羽的，AP2是氢氧化铜的。当进行攻击时，对方的HP减少自己的攻击力，比如HP1＝2 HP2＝1 AP1＝1 AP2＝1，当氢氧化铜攻击枫之羽时，枫之羽的HP＝2(原先的HP1)－1(氢氧化铜的AP2)＝1。现在两个人对决很多回合，每回合不是枫之羽攻击氢氧化铜，就是氢氧化铜攻击枫之羽。求枫之羽能赢氢氧化铜成为下任武林盟主的的胜率。

Input

该题含有多组测试数据,每行为HP1,HP2,AP1和AP2 (1<=HP1,HP2,AP1,AP2<=32767)

Output

每组数据输出一行，为枫之羽赢氢氧化铜概率的值 (结果保留4位小数).

Sample Input


2 1 1 1

Sample Output


75.0000

Source

HDU1410

设枫之羽为A,氢氧化铜为B，根据题目条件，我们可以算出A，B战胜对方分别所需要打的次数如下：

N1 = HP2 / AP1;
N2 = HP1 / AP2;

当不整除时，则需要再多打一下：

if(HP2 % AP1 > 0)
	++N1;
if(HP1 % AP2 > 0)
	++N2;

而A战胜B的情况必定是A打了N1次，且最后一次是A打B。设B打了i次（i < N2），则此种情况发生的概率为：

C(N - 1, i) * pow(0.5, i) * pow(0.5) * N1;

即：

C(N - 1, i) * pow(0.5, N1 + i);

那么A战胜B的概率便是i由0到N2 - 1所有情况中上式的累加。

代码如下：

#include<stdio.h>
#include<cmath>
int main()
{
	int HP1, HP2, AP1, AP2, N1, N2;
	while(scanf("%d%d%d%d", &HP1, &HP2, &AP1, &AP2) != EOF){
		double ans = 0, tmp = 1;
		N1 = HP2 / AP1;
		N2 = HP1 / AP2;
		if(HP2 % AP1 > 0)
			++N1;
		if(HP1 % AP2 > 0)
			++N2;
		ans = pow(0.5, N1);
		for(int i = 1; i < N2; ++i){
			tmp *= (N1 - 1 + i) / i;
			ans += tmp * pow(0.5, N1 + i);
		}
		printf("%.4lf\n", ans * 100);
	}
	return 0;
}

由于浮点数乘除会出现误差，而再乘以一个较大的数会使误差扩大，导致Wrong Answer，因此进行对数转换并进行优化：

#include<stdio.h>
#include<cmath>
int main()
{
	int HP1, HP2, AP1, AP2, N1, N2;
	while(scanf("%d%d%d%d", &HP1, &HP2, &AP1, &AP2) != EOF){
		double ans = 0, tmp = 0;
		N1 = (HP2 - 1) / AP1 + 1;
		N2 = (HP1 - 1) / AP2 + 1;
		ans = pow(0.5, N1);
		for(int i = 1; i < N2; ++i){
			tmp += log10(N1 - 1.0 + i) - log10(i * 1.0);
			ans += pow(10, tmp + (N1 + i) * log10(0.5));
		}
		printf("%.4lf\n", ans * 100);
	}
	return 0;
}

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客