SGU 495.Kids and Prizes

459


题目



点击显/隐题目

ICPC (International Cardboard Producing Company) is in the business of producing cardboard boxes. Recently the company organized a contest for kids for the best design of a cardboard box and selected M winners. There are N prizes for the winners, each one carefully packed in a cardboard box (made by the ICPC, of course). The awarding process will be as follows:

  • All the boxes with prizes will be stored in a separate room.
  • The winners will enter the room, one at a time.
  • Each winner selects one of the boxes.
  • The selected box is opened by a representative of the organizing committee.
  • If the box contains a prize, the winner takes it.
  • If the box is empty (because the same box has already been selected by one or more previous winners), the winner will instead get a certificate printed on a sheet of excellent cardboard (made by ICPC, of course).
  • Whether there is a prize or not, the box is re-sealed and returned to the room.

The management of the company would like to know how many prizes will be given by the above process. It is assumed that each winner picks a box at random and that all boxes are equally likely to be picked. Compute the mathematical expectation of the number of prizes given (the certificates are not counted as prizes, of course).


The first and only line of the input file contains the values of N and M (1 <= N,M <= 100000)


The first and only line of the output file should contain a single real number: the expected number of prizes given out. The answer is accepted as correct if either the absolute or the relative error is less than or equal to 10-9.


5 7
4 3


3.951424
2.3125





题解



可以很容易列出概率dp公式
dp[i] = dp[i-1] / n * dp[i-1] + (n-dp[i]) / n * (dp[i-1] + 1)

由于 i 最大达到 100000
使用递归会爆栈,并且没有必要开数组记录(每个都只计算一次)
也没有必要去推通项公式(不会超时)

直接 for 循环一边算出答案即可
当精度要求能达到全部取走的时候就不用往后算了




也可以从盒子的角度想

m个人是独立的
对于每个礼物不被人选中的概率为 ((n-1)/n)^m
那么不被选中的礼物数的期望就是 n*((n-1)/n)^m
所以答案就是 n-n*((n-1)/n)^m

代码


点击显/隐代码
#include <algorithm>
#include <cstdio>
using namespace std;

const double eps = 1e-12;

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        double ans = 0;
        for (int i = 0; i < m; i++) {
            ans = ((ans * ans) + (n - ans) * (ans + 1)) / n;
            if (fabs(ans - n) < eps)
                break;
        }
        printf("%.11f\n", ans);
    }
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论