微软2017年预科生计划在线编程笔试 第1题 Legendary Items

微软2017年预科生计划在线编程笔试 第1题 Legendary Items

题目1 : Legendary Items

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

Little Hi is playing a video game. Each time he accomplishes a quest in the game, Little Hi has a chance to get a legendary item.

At the beginning the probability is P%. Each time Little Hi accomplishes a quest without getting a legendary item, the probability will go up Q%. Since the probability is getting higher he will get a legendary item eventually.

After getting a legendary item the probability will be reset to ⌊P/(2I)⌋% (⌊x⌋ represents the largest integer no more than x) where I is the number of legendary items he already has. The probability will also go up Q% each time Little Hi accomplishes a quest until he gets another legendary item.

Now Little Hi wants to know the expected number of quests he has to accomplish to get N legendary items.

Assume P = 50, Q = 75 and N = 2, as the below figure shows the expected number of quests is 3.25

2*50%*25% + 3*50%*75%*100% + 3*50%*100%*25% + 4*50%*100%*75%*100% = 3.25
legendary.png

输入

The first line contains three integers P, Q and N.

1 \leq N \leq 10^6, 0 \leq P \leq 100, 1 \leq Q \leq 1001≤N≤106,0≤P≤100,1≤Q≤100

输出

Output the expected number of quests rounded to 2 decimal places.


样例输入

50 75 2

样例输出

3.25

解析

不得不承认,微软在样例中给的二叉树真的十分具有诱惑性,让人第一反应就是模仿这个样子去实现,去计算。为什么呢?
因为用二叉树表现这个概率计算过程,一看就明了,算法都很清晰,剩下的就是去码代码了。

但是,很显然,这样做和暴力解题是差不多的。
就是从N个传奇物品出发,思考所有的可能性,并计算每种可能性的概率。

最终通过数学期望的定义:
   EX=\sum{(X \cdot P(X))}EX=∑(XP(X))

计算想要的结果。

首先,我们要看到的是,这是一道典型的概率计算题目。 每次完成任务,结果无非就是“获得传奇物品”和“未获得物品”。未获得物品时候,我们继续完成任务,这次获得的概率将会变化(不断提高),也就是说,最终必然会获得一个传奇物品。

在思考这个问题的时候,首先要很清晰的认识到每次获得传奇物品这个事件,是相互独立的。获得第一个传奇物品和获得第ii个传奇物品是独立的,即便第ii次的概率是通过[P/2^i][P/2i]计算得到的,但实际上每次的P'P(区别于初始PP)都是固定的。

所以,在计算最终期望的过程中,我们就可以对每次获得传奇物品的任务期望分别计算,最后进行加和,即可得到最终的结果。

根据数学期望的性质:
   E(X+Y)=EX+EYE(X+Y)=EX+EY

所以 EN=E_{(1)}1+E_{(2)}1+E_{(3)}1+.....+E_{(N)}1EN=E(1)​1+E(2)​1+E(3)​1+.....+E(N)​1

而每次获得传奇物品的期望E_{(i)}1E(i)​1计算方法如下:

1.初始任务数(至少1次任务就能获得)numQuests=1numQuests=1
2.第一次任务对该次获得传奇物品增加的期望:incE=(1-P)incE=(1−P)
3.调整概率P=P+QP=P+Q
4.进行下一次任务对该次获得传奇物品增加的期望计算:incE=incE\cdot(1-P)incE=incE⋅(1−P)
5.任务期望:numQuests=numQuest+incEnumQuests=numQuest+incE
6.回到步骤3
7.直至P=P+Q>100P=P+Q>100终止此次获得传奇物品的期望计算numQuestsnumQuests


其实这个代码还可以继续优化,因为在P小于一定值的的时候,后续的传奇物品的期望都是相同的。比如在Q=75Q=75时,P<5P<5后,期望就相同了,不必重复计算。


AC代码(C++):

#include<iostream>
#include<iomanip>

using namespace std;

int main()
{
	int P, Q, N;
	cin >> P >> Q >> N;

	double count_q=Q*1.00/100;
	double count_p;
	double result = 0.00;
	
	for (int i = 1; i <= N; i++)
	{
		double next_result = 1;

		count_p = P*1.00 / 100;
		double E1 = 1.00;
		while (1)
		{
			E1 = E1*(1.00 - count_p);
			next_result += E1;
			count_p += count_q;
			if (count_p > 1.00)
				break;
		}


		result += next_result;
		P = P / 2;
	}

	cout << fixed << setprecision(2) << result;

	return 0;
}

最终结果

编号题目结果语言时间内存
1489Legendary ItemsACG++22ms0MB

发表评论

电子邮件地址不会被公开。 必填项已用*标注