QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#370234#4228. Double SortInfinityNS#AC ✓72ms27868kbC++141.6kb2024-03-28 23:18:532024-03-28 23:18:55

Judging History

你现在查看的是最新测评结果

  • [2024-03-28 23:18:55]
  • 评测
  • 测评结果:AC
  • 用时:72ms
  • 内存:27868kb
  • [2024-03-28 23:18:53]
  • 提交

answer

#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ld long double
using namespace std;
const int N=51,M=10001;
ld nck[M+N][N];
ld nckSum[M+N][N];
ld dp[N][M];
ld ways[N][M];
ld ans[N];
int main(){
    int n,m;
    scanf("%i %i",&n,&m);
    for(int k=0;k<=m+n;k++){
        for(int j=0;j<=n;j++){
            if(j>k)nck[k][j]=0;
            else{
                if(k==0||j==0)nck[k][j]=1;
                else{
                    nck[k][j]=nck[k-1][j-1]+nck[k-1][j];
                }
            }
        }
    }
    for(int i=0;i<=m+n;i++){
        for(int j=0;j<=n;j++){
            nckSum[i][j]=nck[i][j];
            if(i)
            nckSum[i][j]+=nckSum[i-1][j];
            //printf("%i %i: %Lf\n",i,j,nckSum[i][j]);
        }
    }
    ways[n][m]=1;
    for(int sum=m;sum>=0;sum--){
        for(int i=1;i<=n;i++){
            if(sum<i)continue;
            for(int g=0;g<=i;g++){
                ways[i-g][sum-i]+=nck[i][g]*ways[i][sum];
            }
        }
    }
    for(int sum=0;sum<=m;sum++){
        for(int i=1;i<=n;i++){
            if(sum<i)continue;
            ld ww=nckSum[sum-1][i-1];
            //printf("%i %i: %Lf\n",i,sum,ww);
            ww*=ways[i][sum];
            //printf("%i %i: %Lf\n",i,sum,ways[i][sum]);
            for(int j=0;j<i;j++){
                ans[j]+=ww;
            }
        }
    }
    ld ww=nckSum[m-1][n-1];
    for(int i=0;i<n;i++){
        ans[i]/=ww;
    }
    for(int i=n-2;i>=0;i--){
        ans[i]+=ans[i+1];
    }
    for(int i=n-1;i>=0;i--){
        printf("%.10Lf\n",ans[i]);
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3960kb

input:

3 5

output:

1.0000000000
2.3000000000
4.5000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

5 17

output:

1.1313833226
2.7483839690
5.1830963154
8.8556884292
15.0000000000

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 72ms
memory: 27868kb

input:

50 10000

output:

4.4328164335
12.8365968668
25.3152687339
41.9556112383
62.8480760618
88.0871546758
117.7716337788
152.0048947778
190.8952420036
234.5562629251
283.1072243847
336.6735094732
395.3871003913
459.3871135128
528.8203938988
603.8421777570
684.6168328365
771.3186885683
864.1329699727
963.2568520715
1068.90...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 4240kb

input:

40 40

output:

1.0000000000
2.0000000000
3.0000000000
4.0000000000
5.0000000000
6.0000000000
7.0000000000
8.0000000000
9.0000000000
10.0000000000
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
2...

result:

ok 40 numbers

Test #5:

score: 0
Accepted
time: 8ms
memory: 7328kb

input:

39 1489

output:

1.5270875628
3.9390125652
7.3403302435
11.7634937450
17.2367013630
23.7907109205
31.4582877129
40.2742330903
50.2755910473
61.5018753030
73.9953246967
87.8011951264
102.9680947788
119.5483709315
137.5985586446
157.1799042332
178.3589797787
201.2084093701
225.8077336763
252.2444474329
280.6152553480
...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 63ms
memory: 27188kb

input:

47 9871

output:

4.8839175854
14.2093220216
28.0939348059
46.6414309717
69.9602357807
98.1639517434
131.3717230464
169.7086510733
213.3062526631
262.3029665937
316.8447148205
377.0855260737
443.1882307257
515.3252374057
593.6794037510
678.4450160011
769.8288949916
868.0516496140
973.3491031658
1085.9739234660
1206.1...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 7ms
memory: 21324kb

input:

9 9999

output:

111.5562225553
348.0492603945
727.3280017986
1273.1900640301
2018.9521112541
3014.5891397187
4343.3928098375
6171.9464424375
9000.0000000000

result:

ok 9 numbers