poj 6243 Dogs and Cages
Dogs and Cages
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 56 Accepted Submission(s): 40
Special Judge
dogs numbered 0,1,...,N−1
. He also has N
cages numbered 0,1,...,N−1
. Everyday he takes all his dogs out and walks them outside. When he is back
home, as dogs can’t recognize the numbers, each dog just randomly selects a cage
and enters it. Each cage can hold only one dog.
One day, Jerry noticed that
some dogs were in the cage with the same number of themselves while others were
not. Jerry would like to know what’s the expected number of dogs that are NOT in
the cage with the same number of themselves.
cases, T
. T
test cases follow.
Each test case contains only one number N
, indicating the number of dogs and cages.
1≤T≤105
1≤N≤105
#x: y”, where x
is the test case number (starting from 1) and y
is the expected number of dogs that are NOT in the cage with the same number of
itself.
y
will be considered correct if it is within an absolute or relative error of
10−6
of the correct answer.
1
2
Case #2: 1.0000000000
In the first test case, the only dog will enter the only cage. So the answer is 0.
In the second test case, if the first dog enters the cage of the same number, both dogs are in the cage of the same number,
the number of mismatch is 0. If both dogs are not in the cage with the same number of itself, the number of mismatch is 2.
So the expected number is (0+2)/2=1.
思路:和的期望等于期望的和;可以考虑每个位置对总期望的贡献,每个位置满足A[i]!=i有n-1种情况,满足条件的期望为(n-1)/n;
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
typedef vector<double> vec;
typedef vector<vec> mat;
const int N_MAX = ;
double n;
int T; int main() {
scanf("%d", &T);
int k = ;
while (T--) {
k++;
scanf("%lf",&n);
printf("Case #%d: %.10f\n",k,n-);
}
return ;
}
最新文章
- java十进制转十六进制
- Quartus II USB-Blaster驱动解决
- java Collections.sort()实现List排序自定义方法
- Linux:下载方式安装lrzsz
- Web 架构师的能力(转)
- BZOJ4607 : [PA2015 Final]Edycja
- rndc控制远程dns服务器配置方法
- JS实现 键盘操作
- Box2d学习
- CreateCompatibleDC工作原理
- swift 注意事项 (十六) —— 可选链
- linux内核之链表操作解析
- ConOS安装mysql5.7 及简单配置
- spirngMVC的搭建
- Android开发之漫漫长途 XII——Fragment详解
- Django 系列博客(一)
- 使用jquery.mCustomScrollbar自定义滚动条(1)
- 5月14日 绿城育华NOIP巨石杯试卷解析
- Nutch相关视频教程3
- 20155201 实验二《Java面向对象程序设计》实验报告