U716013 PJY 的危险博弈 (PJY's Dangerous Gamble)
题目背景
承接[《BX 的 Bug 依赖链》](https://www.luogu.com.cn/problem/U715985)。
当 BX 在疯狂修 Bug 时,坐在他旁边的 PJY 觉得编程实在太枯燥了,于是打开了后台偷偷刷起了一部悬疑剧。
但是,由于今天的课是严厉的 BY 的课,PJY 每多看一分钟,被抓的风险就会剧增。
作为一个极致的赌徒,PJY 试图在“贪婪地获取看剧快乐”和“被抓导致彻底 GG”之间,找到一条收益最大化的博弈之道。
题目描述
这节课还有 $T$ 分钟下课。
如果 PJY 处于看剧状态,**每连续看 1 分钟,就能获得 1 点快乐值**。
但是,连续看剧的时间越长,被老师注意到的风险就会累积。假设每一分钟结束时,PJY 被抓的概率均为 $P$(单位:万分之一,即 $P = 10000$ 表示 100% 被抓),且每一分钟被抓的事件是相互独立的。这意味着如果 PJY **连续**看了 $k$ 分钟的剧(中间没有切屏),他在这一整个过程中存活下来的概率为 $(1 - \frac{P}{10000})^k$。
如果 PJY 感到危险,他可以选择在任何一分钟的开头,按下 `Alt + Tab` 切回代码界面假装认真敲代码。
这个切屏动作会**消耗整整 1 分钟**的时间。在这一分钟里:
1. 他的连续看剧时长会被**清零**(老师的怀疑度归零)。
2. 他在这一分钟内**无法获得任何快乐值**。
3. 他在这 1 分钟内被抓的概率为 $0\%$(绝对安全)。
4. **最重要的是**:他之前连续看剧积攒的快乐值将被**永久安全地“存入银行”**,即使之后被抓,这部分快乐值也不会丢失。
然而,如果 PJY 贪心不足,在看剧时没有及时切屏,并在第 $k$ 分钟结束时不幸被老师抓到,那么:
1. 他当前这一轮连续看剧所获得的 $k$ 点快乐值会**全部清零**(没来得及存入银行)。
2. 老师会罚他站到走廊上直到下课。这意味着在剩下的时间里,他**再也无法获得任何快乐值**,游戏直接结束。
好消息是,如果 PJY 坚持到了第 $T$ 分钟下课都没有被抓,那么他当时手头上未存入银行的快乐值会自动变得安全。
请你帮 PJY 规划一个最优的切屏策略,使得他在下课时,**期望获得的最终快乐值最大**。
输入格式
第一行包含一个整数 $T$,表示距离下课还有 $T$ 分钟。
第二行包含一个整数 $P$,表示每一分钟被抓的概率(单位:万分之一)。
保证对于任何情况,$0 \le P \le 10000$。
输出格式
输出一个浮点数,表示 PJY 能获得的最大期望快乐值。答案保留两位小数。
说明/提示
**【样例解释 1】**
如果连续看 1 分钟:存活率为 90%。
如果连续看 2 分钟:存活率为 $0.9 \times 0.9 = 0.81$。
最优策略:
- 第 1 分钟:看剧,90% 概率存活,未存入快乐值为 1。10% 概率被抓,GG。
- 第 2 分钟:如果存活,按下 Alt+Tab 切屏。消耗 1 分钟,未存入的 1 点快乐值变安全。
- 第 3 分钟:看剧,90% 概率存活,获得 1 点快乐值(下课自动变安全)。
总期望快乐值 = $0.9 \times (1 + 0.9 \times 1) = 0.9 + 0.81 = 1.71$。
**【样例解释 2】**
如果看 1 分钟切屏,第 1 分钟看剧(50% 存活,获得 1),第 2 分钟切屏。期望为 0.5。
如果连看 2 分钟,第 2 分钟必被抓($P_2=100$),期望为 0。
最大期望为 0.50。
### 数据规模与约定
- **Subtask 0 (10 pts)**:$1 \le T \le 10$,保证 $P \in \{0, 10000\}$
- **Subtask 1 (20 pts)**:$1 \le T \le 2000$。
- **Subtask 2 (30 pts)**:$1 \le T \le 2 \times 10^5$,保证 $P = 5000$。
- **Subtask 3 (40 pts)**:$1 \le T \le 10^6$。
对于 $100\%$ 的数据,保证 $1 \le T \le 10^6$,$0 \le P \le 10000$ 且 $P$ 为整数。