QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#809109#6801. BlackjackWuyanruWA 733ms11772kbC++141.6kb2024-12-11 11:44:372024-12-11 11:44:39

Judging History

This is the latest submission verdict.

  • [2024-12-11 11:44:39]
  • Judged
  • Verdict: WA
  • Time: 733ms
  • Memory: 11772kb
  • [2024-12-11 11:44:37]
  • Submitted

answer

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
ld dp[505][505];
ld fp[505][505];
int a[505];
int n,x,y;
int main()
{
    n=read(),x=read(),y=read();
    for(int i=1;i<=n;i++) a[i]=read();

    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=n-1;j>=0;j--) for(int k=x-a[i];k>=0;k--) dp[j+1][k+a[i]]+=dp[j][k]*(j+1)/(n-j);
        // printf("i=%d : \n",i);
        // for(int j=0;j<=n;j++) for(int k=0;k<=x;k++) if(abs(dp[j][k])>1e-6)
        //     printf("%d %d : %Lf\n",j,k,dp[j][k]);
    }

    ld ans=0;
    for(int i=1;i<=n;i++)
    {
        memcpy(fp,dp,sizeof(fp));
        for(int j=0;j<n;j++) for(int k=0;k<=x;k++)
        {
            ld &val=fp[j][k];
            if(val<1e-20) val=0;
            if(val>1-1e-20) val=1;
            if(j<n&&j+a[i]<=x) fp[j+1][k+a[i]]-=val*(j+1)/(n-j);
            if(k<=x&&k+a[i]>y)
            {
                ans+=fp[j][k]/(n-j);
                // if(abs(fp[j][k])>1e-6) printf("i=%d j=%d k=%d : %Lf\n",i,j,k,fp[j][k]/(n-j));
            }
        }
    }
    printf("%.10Lf\n",1-ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9776kb

input:

5 2 4
1 1 1 5 5

output:

0.1000000000

result:

ok found '0.1000000', expected '0.1000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 9816kb

input:

5 2 4
1 1 1 3 5

output:

0.4500000000

result:

ok found '0.4500000', expected '0.4500000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 3ms
memory: 8768kb

input:

18 10 11
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

output:

0.0000000000

result:

ok found '0.0000000', expected '-0.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 5ms
memory: 8400kb

input:

14 15 16
3 3 3 3 3 3 3 3 3 3 3 3 3 3

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #5:

score: 0
Accepted
time: 4ms
memory: 9480kb

input:

7 20 23
4 4 4 4 4 4 4

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 9784kb

input:

10 25 27
5 5 5 5 5 5 5 5 5 5

output:

-0.0000000000

result:

ok found '-0.0000000', expected '0.0000000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 3ms
memory: 8028kb

input:

6 30 35
6 6 6 6 6 6

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #8:

score: 0
Accepted
time: 3ms
memory: 7928kb

input:

9 35 36
7 7 7 7 7 7 7 7 7

output:

0.0000000000

result:

ok found '0.0000000', expected '-0.0000000', error '-0.0000000'

Test #9:

score: 0
Accepted
time: 6ms
memory: 9436kb

input:

14 33 40
8 8 8 8 8 8 8 8 8 8 8 8 8 8

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #10:

score: 0
Accepted
time: 4ms
memory: 9524kb

input:

7 43 45
9 9 9 9 9 9 9

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #11:

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

input:

7 49 50
10 10 10 10 10 10 10

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 9336kb

input:

7 49 55
11 11 11 11 11 11 11

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 8000kb

input:

16 53 60
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 7920kb

input:

16 53 65
13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 8816kb

input:

10 55 60
8 2 8 10 8 8 1 2 8 10

output:

0.5638888889

result:

ok found '0.5638889', expected '0.5638889', error '0.0000000'

Test #16:

score: 0
Accepted
time: 0ms
memory: 8320kb

input:

10 38 43
5 8 1 9 7 2 1 9 3 1

output:

0.4888888889

result:

ok found '0.4888889', expected '0.4888889', error '0.0000000'

Test #17:

score: 0
Accepted
time: 0ms
memory: 8636kb

input:

10 49 52
8 2 8 10 6 2 10 5 1 5

output:

0.3861111111

result:

ok found '0.3861111', expected '0.3861111', error '0.0000000'

Test #18:

score: 0
Accepted
time: 0ms
memory: 9204kb

input:

10 44 49
3 10 3 2 7 5 5 10 5 4

output:

0.6777777778

result:

ok found '0.6777778', expected '0.6777778', error '0.0000000'

Test #19:

score: 0
Accepted
time: 0ms
memory: 9804kb

input:

10 54 58
5 9 8 2 4 3 8 7 7 6

output:

0.3000000000

result:

ok found '0.3000000', expected '0.3000000', error '0.0000000'

Test #20:

score: 0
Accepted
time: 0ms
memory: 8412kb

input:

10 46 49
2 2 3 9 9 3 4 5 7 7

output:

0.5000000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #21:

score: 0
Accepted
time: 4ms
memory: 8196kb

input:

10 50 51
10 9 10 4 8 2 1 1 2 10

output:

0.0575396825

result:

ok found '0.0575397', expected '0.0575397', error '0.0000000'

Test #22:

score: 0
Accepted
time: 4ms
memory: 8436kb

input:

10 35 39
8 6 4 1 3 1 9 6 2 3

output:

0.5888888889

result:

ok found '0.5888889', expected '0.5888889', error '0.0000000'

Test #23:

score: 0
Accepted
time: 4ms
memory: 9176kb

input:

10 62 64
10 8 7 4 4 7 10 10 8 1

output:

0.0444444444

result:

ok found '0.0444444', expected '0.0444444', error '0.0000000'

Test #24:

score: 0
Accepted
time: 4ms
memory: 8168kb

input:

10 40 41
2 2 2 4 6 4 4 6 5 10

output:

0.3666666667

result:

ok found '0.3666667', expected '0.3666667', error '0.0000000'

Test #25:

score: -100
Wrong Answer
time: 733ms
memory: 11772kb

input:

500 392 500
21 90 87 268 118 213 27 34 32 41 186 21 116 237 110 219 115 117 118 407 298 123 111 170 273 451 273 206 122 333 249 85 53 414 254 71 305 2 287 370 440 397 158 471 406 425 161 200 355 338 44 421 27 132 236 439 428 353 22 125 269 208 373 130 213 272 403 203 60 127 378 126 383 417 320 439 9...

output:

0.4705801925

result:

wrong answer 1st numbers differ - expected: '0.4703331', found: '0.4705802', error = '0.0002471'