SGU495Kids and Prizes(数学期望||概率DP||公式)
495. Kids and Prizes
Memory limit: 262144 kilobytes
output: standard
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 ().
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.
sample input |
sample output |
5 7 |
3.951424 |
sample input |
sample output |
4 3 |
2.3125 |
Online Contester Team © 2002 - 2010. All rights reserved. |
InputThe first and only line of the input file contains the values of N and M ().OutputThe 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.Sample Input
sample input |
sample output |
5 7 |
3.951424 |
sample input |
sample output |
4 3 |
2.3125 |
题意:
有n个奖品,m个人排队来选礼物,对于每个人,他打开的盒子,可能有礼物,也有可能已经被之前的人取走了。为最后m个人取走礼物的期望。
思路:
排队取,第1个人取到1个,dp[1]=1;后面的人dp[i]=p取到礼物盒子+dp取到礼物=(n-dp[i-1])/n + dp[i-1];
当然,也可以化简为公式 printf("%.10lf\n",n*1.0*(1-pow((n-1)*1.0/n,m)));
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<algorithm>
using namespace std;
double dp[];
int main()
{
int n,m,i;
while(~scanf("%d%d",&n,&m)){
dp[]=;
for(i=;i<=m;i++) dp[i]=dp[i-]+(n-dp[i-])/n;
printf("%.9lf\n",dp[m]);
}return ;
}
最新文章
- xml格式的数据转化成数组
- JS中的属性和变量的区别
- ios--Attributes和ParagraphStyle介绍
- 文件TEXTBOX
- Maintainable JavaScript(编写可维护的JavaScript) PART I Style Guidelines
- [Hapi.js] Replying to Requests
- linux时间校准设置,解决与本地时间不一致问题
- 在Ubuntu Linux下制作Windows 启动安装 USB盘
- HDU 2389 Rain on your Parade 最大匹配(模板题)【HK算法】
- rem自适应手机端布局
- poi操作Excel的封装类
- 2019.02.12 bzoj3944: Sum(杜教筛)
- pandas网页操作基础
- (原)Echarts 报Uncaught Error: Initialize failed: invalid dom 根本解决
- Mac IntelliJ IDEA 2017(java开发集成环境)附注册码和破解教程 v2017.3.5破解版
- Atitit 软件项目系统托盘图标解决方案
- CI框架 -- 核心文件 之 Loader.php(加载器)
- Java中统计字符串中各个字符出现的次数
- 【ARC072F】 Dam 单调队列
- 四则运算之GUI