P3682. 亚瑟王的生日庆典

题目描述

亚瑟王是一个自恋的人，他打算不惜花费大量金币来庆祝他的第$K$个生日。这场奢华的庆典将从他的生日当天开始，而亚瑟王决定让命运来决定何时结束。每天，他会掷一枚硬币，这枚硬币有$p$的概率正面朝上，$1-p$的概率反面朝上。庆典将持续进行，直到硬币累计出现$K$次正面为止。此外，国王还决定：

• 第$1$天的庆典花费$1$千枚金币，
• 第$2$天的花费为$3$千枚金币，
• 第$3$天的花费为$5$千枚金币，
• 以此类推，每一天的花费比前一天多$2$千枚金币。

你能告诉大臣，庆典预计会持续多少天，以及预计总共会花费多少金币吗？

输入格式

输入包含多个测试用例。
每个测试用例占一行，包含一个整数$K$（$0 < K \leq 1000$）和一个实数$p$（$0.1 \leq p \leq 1$）。
输入以单独的一行$0$结束。

输出格式

对于每个测试用例，输出两个数字——期望的天数和期望的金币花费（单位：千枚），结果保留$3$位小数。

输入样例 1

1 1  
1 0.5  
0  

输出样例 1

1.000 1.000  
2.000 6.000  

来源

POJ Founder Monthly Contest – 2008.08.31, Soduku@POJ

数学公式说明

1. 期望天数：这是一个**负二项分布（Negative Binomial Distribution）**问题，期望值为$E[\text{days}] = \frac{K}{p}$。
2. 期望花费：每天的花费构成一个等差数列，第$n$天的花费为$2n-1$千枚金币。总花费的期望可以表示为：$$E[\text{cost}] = \sum_{n=1}^{\infty} (2n-1) \cdot P(\text{庆典在第 } n \text{ 天仍进行}) $$经过推导，可以得到$E[\text{cost}] = \frac{K}{p} + \frac{2K(1-p)}{p^2}$。

示例解释

• 输入 1 1：硬币每次必为正面（$p=1$），因此只需$1$天，花费$1$千枚金币。
• 输入 1 0.5：硬币正反面概率各$50\%$，期望$2$天结束，总花费$1 + 3 = 4$千枚金币（但实际计算需考虑概率分布，最终期望为$6$千枚）。