Submission #1368206
Source Code Expand
#include <fstream>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <random>
using namespace std;
#define min(a,b) ((a)<(b) ? (a):(b))
#define max(a,b) ((a)>(b) ? (a):(b))
//INT_MAX
//LONG_LONG_MAX
long long maxd(long long a,long long b){
if(a>=b){
return a;
}
return b;
}
long long mind(long long a,long long b){
if(a<=b){
return a;
}
return b;
}
long long gcd(long long a, long long b){
if(a<b){
swap(a,b);
}
while(b){
long long r = a%b;
a=b;
b=r;
}
return a;
}
long long lcm(long long a, long long b){
return (a*b)/gcd(a,b);
}
int isPrim(int a){
if(a==1){
return 0;
}
for(int i=2;i<=(a+1)/2;i++){
if(a%i==0){
return 0;
}
}
return 1;
}
long long mod_pow(long long x, long long n, long long mod){
//xのn乗を計算するのにn乗を2進表記にして計算
//x^22 = x^16 + x^4 + x^2
long long ret=1;
while(n>0){
if(n%2==1){
ret=(ret*x)%mod;//答えに付加
}
x=(x*x)%mod;//2乗
n=n/2;
}
return ret;
}
struct XX{
long long a;
int i;
};
class xxIntu {
public:
bool operator()(const XX& riLeft, const XX& riRight) const {
//第2条件
if((riLeft.a) == (riRight.a)){
return riLeft.i < riRight.i;//<:昇順(小さいものから順番)、>:降順(大きいものから順番)
}
//第1条件
return (riLeft.a) < (riRight.a);
}
};
class xxGreater {
public:
bool operator()(const XX& riLeft, const XX& riRight) const {
//第2条件
if((riLeft.a) == (riRight.a)){
return riLeft.i > riRight.i;//<:昇順(小さいものから順番)、>:降順(大きいものから順番)
}
//第1条件
return (riLeft.a) > (riRight.a);
}
};
//int ppar[200001];
//int rrank[200001];
//
//void init(int n){
// for(int i=1;i<=n;i++){
// ppar[i]=i;
// rrank[i]=0;
// }
//}
//
//int find(int x){
// if(ppar[x]==x){
// return x;
// }else{
// return ppar[x]=find(ppar[x]);
// }
//}
//
//void unite(int x,int y){
// x=find(x);
// y=find(y);
// if(x==y){
// return;
// }
// if(rrank[x]<rrank[y]){
// ppar[x]=ppar[y];
// }else{
// ppar[y]=x;
// if(rrank[x]==rrank[y]){
// rrank[x]++;
// }
// }
//}
//bool same(int x,int y){
// return find(x)==find(y);
//}
//kruskal
//struct edge{
// int u;
// int v;
// int cost;
//};
//
//bool comp(edge& e1,edge& e2){
// return e1.cost < e2.cost;
//}
//
//edge es[2000];
//int V,E;
//int ans=0;
//int kruskal(){
// sort(es,es+E,comp);
// init(V);
// int res = 0;
// for(int i=0;i<E;i++){
// edge e = es[i];
// if(!same(e.u,e.v)){
// unite(e.u,e.v);
// res+=e.cost;
// ans++;
// }
// }
// return res;
//}
//
//
//struct edge{
// long to;
// long cost;
//};
//typedef pair<long,long> P;//first:最短距離、second:頂点番号
//long V;
//vector<edge>G[1001];//G[各頂点番号]
//long d[1001];
//
//int dijkstra(long s){
// priority_queue<P,vector<P>> que;
// fill(d,d+V+1,-9223372036854775807);
// d[s]=0;
// que.push(P(0,s));
//
// int index=0;
// while(!que.empty()){
// P p=que.top();
// que.pop();
// long v=p.second;
// if(d[v]<p.first){
// continue;
// }
// for(int i=0;i<G[v].size();i++){
// edge e=G[v][i];
// if(d[e.to]<d[v]+e.cost){
// d[e.to]=d[v]+e.cost;
// que.push(P(d[e.to],e.to));
// }
// }
//
// if(index++>4000000){
// return -1;
// }
// }
// return 0;
//}
int main(int argc, const char * argv[])
{
//std::ios::sync_with_stdio(false);
//scanf("%s",S);
//scanf("%d",&N);
//sscanf(tmp.c_str(),"%dd%d%d",&time[i], &dice[i], &z[i]);
//getline(cin, target);
//cin >> x >> y;
//テスト用
//ifstream ifs( "1_06.txt" );
//ifs >> a;
//ここから
int N,A,B;
cin >> N >> A >>B;
long long v[50];
for(int i=0;i<N;i++){
cin >> v[i];
}
sort(v,v+N,greater<long long>());
if(v[0]==v[A-1]){
double sum=0;
for(int i=0;i<A;i++){
sum+=v[i];
}
printf("%.7f\n",sum/A);
double cnt=0;
for(int i=0;i<N;i++){
if(v[0]!=v[i]){
break;
}
cnt++;
}
long long ans=0;
for(long long j=0;j<=B-A;j++){
double tmp=1;
//cntからA個えらぶ
for(double i=0;i<A+j;i++){
if(i!=0){
tmp*=(cnt-i)/(i+1);
}else{
tmp*=cnt;
}
}
ans+=tmp;
}
cout << ans << endl;
return 0;
}else{
double sum=0;
for(int i=0;i<A;i++){
sum+=v[i];
}
printf("%.7f\n",sum/A);
double cnt=0;
for(int i=A;i>=0;i--){
if(v[A-1]!=v[i]){
break;
}
cnt++;
}
double zen=cnt;
for(int i=A;i<N;i++){
if(v[A-1]!=v[i]){
break;
}
zen++;
}
double tmp=1;
//zenからcnt個えらぶ
for(double i=0;i<cnt;i++){
if(i!=0){
tmp*=(zen-i)/(i+1);
}else{
tmp*=cnt;
}
}
cout << (long long)tmp << endl;
return 0;
}
//cout << ans << endl;
//ここまで
//cout << "ans" << endl;改行含む
//printf("%.0f\n",ans);//小数点以下表示なし
//printf("%.7f\n",p);
//printf("%f\n",pow(2,ans.size()));
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Maximum Average Sets |
User |
ikeha |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
6514 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
sample_04.txt |
AC |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
1 ms |
256 KB |
subtask_1_10.txt |
AC |
1 ms |
256 KB |
subtask_1_11.txt |
AC |
1 ms |
256 KB |
subtask_1_12.txt |
AC |
1 ms |
256 KB |
subtask_1_13.txt |
AC |
1 ms |
256 KB |
subtask_1_14.txt |
AC |
1 ms |
256 KB |
subtask_1_15.txt |
AC |
1 ms |
256 KB |
subtask_1_2.txt |
AC |
1 ms |
256 KB |
subtask_1_3.txt |
AC |
1 ms |
256 KB |
subtask_1_4.txt |
AC |
1 ms |
256 KB |
subtask_1_5.txt |
AC |
1 ms |
256 KB |
subtask_1_6.txt |
AC |
1 ms |
256 KB |
subtask_1_7.txt |
AC |
1 ms |
256 KB |
subtask_1_8.txt |
AC |
1 ms |
256 KB |
subtask_1_9.txt |
AC |
1 ms |
256 KB |