King Arthur's Birthday Celebration(POJ 3682)

Problem Description

King Arthur is an narcissist who intends to spare no coins to celebrate his coming K-th birthday. The luxurious celebration will start on his birthday and King Arthur decides to let fate tell when to stop it. Every day he will toss a coin which has probability p that it comes up heads and 1-p up tails. The celebration will be on going until the coin has come up heads for K times. Moreover, the king also decides to spend 1 thousand coins on the first day's celebration, 3 thousand coins on the second day's, 5 thousand coins on the third day's ... The cost of next day will always be 2 thousand coins more than the previous one's. Can you tell the minister how many days the celebration is expected to last and how many coins the celebration is expected to cost?

Input

The input consists of several test cases.
For every case, there is a line with an integer K ( 0 < K ≤ 1000 ) and a real number p (0.1 ≤ p ≤ 1).
Input ends with a single zero.

Output

For each case, print two number -- the expected number of days and the expected number of coins (in thousand), with the fraction rounded to 3 decimal places.

Sample Input

1 1
1 0.5
0

Sample Output

1.000 1.000
2.000 6.000

My Code

期望dp，当然大佬都是直接求出通项的。

E[i]为获得抛出i次正面的期望天数，这个其实可以直接想到，每天抛出正面的概率是p，抛出i次正面就需要i/p天。用dp的话，分两种情况，第一种，前面抛出了i-1次，这次抛出了正面，第二种，前面抛出了i次正面，这次抛出了反面。所以可以得到E[i]=p*E[i-1]+(1-p)*E[i]+1。因为无论抛出正面还是反面天数都要加1.

F[i]就是抛出i次正面的期望金钱，第i天花费的金钱为2*i-1，下一天就是2*i+1，和上面推导差不多，递推公式为F[i]=p*(F[i-1]+2*E[i-1]+1)+(1-p)*(F[i]+2*E[i]+1)，然后再化简一下就好了。

#include 
#include 
#define maxn 1005
using namespace std;

double E[maxn];
double F[maxn];
int k;
double p;
int main()
{
    while (cin >> k && k)
    {
        cin >> p;
        E[0] = 0;
        F[0] = 0;
        for (int i = 1; i <= k; i++)
        {
            E[i] = i / p;   //E(i)=p*E(i-1)+(1-p)*E(i)+1
            F[i] = F[i - 1] + 2 * E[i - 1] + 2 * (1 - p) / p * E[i] + 1 / p;
        }   //F(i)=p*(F(i-1)+2*E(i-1)+1)+(1-p)*(F(i)+2*E(i)+1)
        printf("%.3f %.3f
", E[k], F[k]);//g++用%lf会WA，C++用%lfAC
    }
    return 0;
}