Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem A
Expect the Expected
Input: Standard Input

Output: Standard Output

Some mathematical background. This problem asks you to compute the expected value of a random variable. If you haven't seen those before, the simple definitions are as follows. A random variable is a variable that can have one of several values, each with a certain probability. The probabilities of each possible value are positive and add up to one. The expected value of a random variable is simply the sum of all its possible values, each multiplied by the corresponding probability. (There are some more complicated, more general definitions, but you won't need them now.) For example, the value of a fair, 6-sided die is a random variable that has 6 possible values (from 1 to 6), each with a probability of 1/6. Its expected value is 1/6 + 2/6 + ... + 6/6 = 3.5. Now the problem.

I like to play solitaire. Each time I play a game, I have probability p of solving it and probability (1-p) of failing. The game keeps statistics of all my games - what percentage of games I have won. If I simply keep playing for a long time, this percentage will always hover somewhere around p*100%. But I want more.

Here is my plan. Every day, I will play a game of solitaire. If I win, I'll go to sleep happy until the next day. If I lose, I'll keep playing until the fraction of games I have won today becomes larger than p. At this point, I'll declare victory and go to sleep. As you can see, at the end of each day, I'm guaranteed to always keep my statistics above the expected p*100%. I will have beaten mathematics!

If your intuition is telling you that something here must break, then you are right. I can't keep doing this forever because there is a limit on the number of games I can play in one day. Let's say that I can play at most n games in one day. How many days can I expect to be able to continue with my clever plan before it fails? Note that the answer is always at least 1 because it takes me a whole day of playing to reach a failure.

Input

The first line of input gives the number of cases, N. N test cases follow. Each one is a line containing p (as a fraction) and n.

1 ≤ N ≤ 3000, 0 ≤ p < 1,

The denominator of p will be at most 1000,

1 ≤ n ≤ 100.

Output

For each test case, print a line of the form "Case #x: y", where y is the expected number of days, rounded down to the nearest integer. The answer will always be at most 1000 and will never be within 0.001 of a round-off error case.

Sample Input                                Output for Sample Input

4

1/2 1

1/2 2

0/1 10

1/2 3

Case #1: 2

Case #2: 2

Case #3: 1

Case #4: 2

Problemsetter: Igor Naverniouk

Special thanks: Frank Chu

題目描述：

一場遊戲獲勝的機率為 p, 而一天最多玩 n 場遊戲, 然後每一天的遊戲都會玩到勝率大於 p 便會停止。
問玩遊戲天數的期望值為何?

題目解法：

實質上要計算出一天無法獲勝的機率 q, 那麼天數的期望值就是 1/q

dp[i][j]=dp[i-1][j-1]*p+dp[i-1][j]*(1-p)

i 為玩了幾場, j 是勝了幾場

因此在轉換的時候會捨去掉勝率大於 p 的轉換。

#include <stdio.h>
#include <string.h>
double dp[105][105];
int main() {
    int testcase, cases = 0;
    int a, b, n;
    int i, j;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d/%d %d", &a, &b, &n);
        double p = ((double)a)/b;
        memset(dp, 0, sizeof(dp));
        dp[1][0] = 1-p;
        for(i = 2; i <= n; i++) {
            for(j = 0; j <= i*p; j++) {
                if(j)
                    dp[i][j] += dp[i-1][j-1]*p;
                dp[i][j] += dp[i-1][j]*(1-p);
            }
        }
        double ret = 0;
        for(i = 0; i <= n*p; i++)
            ret += dp[n][i];
        printf("Case #%d: %d\n", ++cases, (int)(1/ret));
    }
    return 0;
}