Andrew and Jerry are playing a game with Harry as the scorekeeper. The game consists of three rounds. In each round, Andrew and Jerry draw randomly without replacement from a jar containing n balls, each labeled with a distinct positive integer. Without looking, they hand their balls to Harry, who awards the point to the player with the larger number and returns the balls to the jar. The winner of the game is the one who wins at least two of the three rounds.
Andrew wins rounds 1 and 2 while Jerry wins round 3, so Andrew wins the game. However, Jerry is unhappy with this system, claiming that he will often lose the match despite having the higher overall total. What is the probability that the sum of the three balls Jerry drew is strictly higher than the sum of the three balls Andrew drew?
Input
The first line of input contains a single integer n (2 ≤ n ≤ 2000) — the number of balls in the jar.
The second line contains n integers ai (1 ≤ ai ≤ 5000) — the number written on the ith ball. It is guaranteed that no two balls have the same number.
Output
Print a single real value — the probability that Jerry has a higher total, given that Andrew wins the first two rounds and Jerry wins the third. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.
Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .
Hint
In the first case, there are only two balls. In the first two rounds, Andrew must have drawn the 2 and Jerry must have drawn the 1, and vice versa in the final round. Thus, Andrew's sum is 5 and Jerry's sum is 4, so Jerry never has a higher total.
In the second case, each game could've had three outcomes — 10 - 2, 10 - 1, or 2 - 1. Jerry has a higher total if and only if Andrew won 2 - 1 in both of the first two rounds, and Jerry drew the 10 in the last round. This has probability .
简单dp一下解决。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=;
int n,a[N];
double dp[N],p[N],ans;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
sort(a+,a+n+);
for(int i=;i<=n;i++)
for(int j=;j<i;j++)
p[a[i]-a[j]]+=2.0/(n*(n-));
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(i+j<=)dp[i+j]+=p[i]*p[j];
for(int i=;i<=;i++)
for(int j=;j<i;j++)
ans+=p[i]*dp[j];
printf("%.10lf\n",ans);
return ;
}
数学(概率)CodeForces 626D:Jerry's Protest的更多相关文章
-
Codeforces 626D Jerry&#39;s Protest(暴力枚举+概率)
D. Jerry's Protest time limit per test:2 seconds memory limit per test:256 megabytes input:standard ...
-
Codeforces 626D Jerry&#39;s Protest 「数学组合」「数学概率」
题意: 一个袋子里装了n个球,每个球都有编号.甲乙二人从每次随机得从袋子里不放回的取出一个球,如果甲取出的球比乙取出的球编号大则甲胜,否则乙胜.保证球的编号xi各不相同.每轮比赛完了之后把取出的两球放 ...
-
CodeForces 626D Jerry&#39;s Protest
计算前两盘A赢,最后一盘B赢的情况下,B获得的球的值总和大于A获得的球总和值的概率. 存储每一对球的差值有几个,然后处理一下前缀和,暴力枚举就好了...... #include<cstdio&g ...
-
8VC Venture Cup 2016 - Elimination Round D. Jerry&#39;s Protest 暴力
D. Jerry's Protest 题目连接: http://www.codeforces.com/contest/626/problem/D Description Andrew and Jerr ...
-
Codeforces Round #370 (Div. 2) E. Memory and Casinos (数学&;&;概率&;&;线段树)
题目链接: http://codeforces.com/contest/712/problem/E 题目大意: 一条直线上有n格,在第i格有pi的可能性向右走一格,1-pi的可能性向左走一格,有2中操 ...
-
codeforces626D . Jerry's Protest (概率)
Andrew and Jerry are playing a game with Harry as the scorekeeper. The game consists of three rounds ...
-
codeforces 711E E. ZS and The Birthday Paradox(数学+概率)
题目链接: E. ZS and The Birthday Paradox. time limit per test 2 seconds memory limit per test 256 megaby ...
-
CodeForces 621C 数学概率期望计算
昨天训练赛的题..比划了好久才想出来什么意思 之前想的是暴力for循环求出来然后储存数组 后来又想了想 自己萌的可以.. 思路就是求出来每个人与他的右边的人在一起能拿钱的概率(V(或)的关系)然后*2 ...
-
【数学】Codeforces 707C Pythagorean Triples
题目链接: http://codeforces.com/problemset/problem/707/C 题目大意: 给你一个数,构造其余两个勾股数.任意一组答案即可,没法构造输出-1. 答案long ...
随机推荐
-
FFmpeg学习5:多线程播放视音频
在前面的学习中,视频和音频的播放是分开进行的.这主要是为了学习的方便,经过一段时间的学习,对FFmpeg的也有了一定的了解,本文就介绍了 如何使用多线程同时播放音频和视频(未实现同步),并对前面的学习 ...
-
win10 Edge浏览器一打开就闪退崩溃的解决思路
故障现象:从Win7.Win8.1升级到Win10,或是使用Win10一段时间后,发现Edge浏览器打开一到两秒就闪退,崩溃无法打开.解决方案: 1.尝试清理: C:\Users\Administra ...
-
Css3_必备10个东西
1.边框圆角(Border Radiuas) 这个是我们在平常很常用的吧,以前我在用div圆角的时候,特别特别的痛苦,不管是用CSS来画圆角,还是用图片来画圆角都不那么容易,但是现在好了,在CSS3中 ...
-
Regional Changchun Online--Elven Postman(裸排序二叉树)
Elven Postman Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Tot ...
-
下载doxygen
官网首页:http://www.stack.nl/~dimitri/doxygen/index.html 下载页面:http://www.stack.nl/~dimitri/doxygen/downl ...
-
[前端]如何写一个水平导航栏?(浮动、inline-block+消除间距)
在看W3school时,看到一个很好的例子,如何制作一个水平的导航栏?没有任何要求,只需要达到下面的效果: 我认为这个例子包含了很多css布局需要了解的知识,因此单独写一下. W3school上面的方 ...
-
JS学习笔记Day21
一.mySQL数据库 (一)数据库的概念 1.概念:可以存储数据的一个仓库 2.结构化数据:以表格的形式展现,结构更清晰,这样的数据称之为结构化数据 (二)数据库管理软件 1.一种对数据库文件进行管理 ...
-
AWS MVC 详解
由于新工作是在AWS PaaS平台上进行开发,为不耽误工作,先整理一下AWS MVS的使用规范,快速上手.对AWS PaaS平台的相关介绍留到以后再来补充.本文几乎是对官方学习文档的整理,有遗漏的后补 ...
-
共享权限ACL列表出现SID现象
http://www.minasi.com/forum/topic.asp?TOPIC_ID=16842 Basically here's what happens, and why it doesn ...
-
zmediaboard-Hi3518参数及配置
1.12_13.uboot的烧写和flash分区1_21.12.1.裸机烧录uboot(1)什么叫裸机烧录?设备是空白的,未经烧录的,就叫裸机.(2)裸机烧录一个设备有2种方案:1是用外部烧录器来烧录 ...