QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#711577#6565. Game Show Eliminationucup-team902WA 125ms16980kbC++203.8kb2024-11-05 12:11:402024-11-05 12:11:40

Judging History

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

  • [2024-11-05 12:11:40]
  • 评测
  • 测评结果:WA
  • 用时:125ms
  • 内存:16980kb
  • [2024-11-05 12:11:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using db=double;
const int N=1000,K=1<<9;
const db eps=1e-9;
int n,k;
db g[12][K+5][12],f[N+5][12][K+5];
db ans[N+5];
int getv(int x,int d){
    return x==k?0:x==k+1?d:-x-1;
}
db work(int d,int s,int pos,int mx){
    if(pos==mx) return 0;
    mx=getv(mx,d);
    pos=getv(pos,d);
    // printf("%d %d\n",mx,pos);
    static db h[12];
    db res=0;
    for(int v=pos;v<pos+k;v++){
        memset(h,0,sizeof h);
        h[0]=1;
        for(int i=0;i<=k+1;i++)
            if((s>>i&1)||(i>=k)){
                int vi=getv(i,d);
                if(vi==pos) continue;
                if(vi!=mx){
                    if(v<vi)
                        memset(h,0,sizeof h);
                    else if(v<vi+k){
                        for(int j=k;j;j--)
                            h[j]=h[j-1]+(v-vi)*h[j];
                        h[0]*=(v-vi);
                        for(int j=0;j<=k;j++) h[j]/=k;
                    }
                }
                else{
                    if(v>=vi+k)
                        memset(h,0,sizeof h);
                    else if(v>=vi){
                        for(int j=k;j;j--)
                            h[j]=h[j]*(vi+k-v)-h[j-1];
                        h[0]*=(vi+k-v);
                        for(int j=0;j<=k;j++) h[j]/=k;
                    }
                }
            }
        for(int i=0;i<=k;i++)
            res+=h[i]/(i+1);
        // printf("%lf\n",res);
    }
    return res/k;
}
void prep(){
    for(int i=1;i<=k;i++)
        for(int s=0;s<(1<<k-1);s++){
            for(int j=0;j<=k+1;j++){
                if((s>>j&1)||j>=k){
                    int mx;
                    for(mx=0;mx<k;mx++)
                        if((s>>mx&1)&&(-mx-1+k>i))
                            g[i][s][j]+=work(i,s,j,mx);
                    g[i][s][j]+=work(i,s,j,k);
                    g[i][s][j]+=work(i,s,j,k+1);
                }
            }
        }
}
int popc(int s){
    int res=0;
    for(;s;s&=s-1) res++;
    return res;
}
int main(){
    scanf("%d %d",&n,&k);
    prep();
    f[n-1][1][(1<<min(k-1,n-2))-1]=1;
    for(int i=n-1;i;i--){
        int rk=min(i-1,k-1);
        for(int j=1;j<=k;j++){
            for(int s=(1<<rk)-1;s>=0;s--){
                if(f[i][j][s]<eps) continue;
                int crk=i-rk+1+popc(s);
                for(int l=0;l<rk;l++)
                    if(s>>l&1){
                        db c=f[i][j][s]*g[j][s][l];
                        ans[i-l-1]+=c*crk;
                        f[i][j][s^(1<<l)]+=c;
                    }
                if(crk==2){
                    db c1=f[i][j][s]*g[j][s][k];
                    db c2=f[i][j][s]*g[j][s][k+1];
                    ans[i]+=c1*2+c2;
                    if(j<k)
                        ans[i+j]+=c2*2+c1;
                }
                else{
                    int ni=i-1,ns=s|(1<<k-1);
                    while(1){
                        if(ns&1){
                            ns>>=1;
                            break;
                        }
                        ni--;
                        ns=(ns>>1)|(1<<k-1);
                    }
                    ns&=(1<<min(ni-1,k-1))-1;
                    db c=f[i][j][s]*g[j][s][k];
                    ans[i]+=c*crk;
                    int nd=i+j-ni;
                    if(j<k&&nd>=k)
                        ans[i+j]+=c;
                    nd=min(nd,k);
                    f[ni][nd][ns]+=c;
                    if(j<k){
                        c=f[i][j][s]*g[j][s][k+1];
                        nd=i-ni;
                        ans[i+j]+=c*crk;
                        f[ni][nd][ns]+=c;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%.13lf\n",ans[i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2

output:

2.1093750000000
2.6250000000000
1.2656250000000

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 125ms
memory: 16980kb

input:

1000 10

output:

2.9271626093194
3.5371582643783
4.2809911642031
5.1309917592025
6.0536627885309
7.0188755594386
8.0053455536222
9.0008899053761
9.9997196746692
10.9995100137400
11.9994656656443
12.9994213561075
13.9993770851297
14.9993328527109
15.9992886588511
16.9992445035503
17.9992003868084
18.9991563086257
19....

result:

wrong answer 1st numbers differ - expected: '2.9272933', found: '2.9271626', error = '0.0000447'