0%

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

## 输入

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 100\

## 输出

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

# 解析

$EX=\sum{(X \cdot P(X))}$

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

$EN=E_{(1)}1+E_{(2)}1+E_{(3)}1+.....+E_{(N)}1$

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

## 最终结果

1489 Legendary Items AC G++ 22ms 0MB