# 题目1 : Legendary Items

## 描述

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


## 输入

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

# 解析

EX=\sum{(X \cdot P(X))}EX=∑(X⋅P(X))

E(X+Y)=EX+EYE(X+Y)=EX+EY

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

## 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