[ACM_HDU_1410]PK武林盟主

蓝飞 蓝飞 | 时间:2012-04-20, Fri | 13,071 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;
}
如需转载请注明出处:蓝飞技术部落格

当前暂无评论 »