QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412928#6565. Game Show Eliminationgrass8cowAC ✓65ms66132kbC++173.2kb2024-05-16 21:45:262024-05-16 21:45:26

Judging History

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

  • [2024-05-16 21:45:26]
  • 评测
  • 测评结果:AC
  • 用时:65ms
  • 内存:66132kb
  • [2024-05-16 21:45:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define db double
int m,e;
ll f[12];
vector<db>sol(vector<int>l){
    vector<db>an;
    int n=l.size();for(int i=0;i<n;i++)an.pb(0);
    for(int i=0;i<n;i++){
        for(int d=l[i];d<l[i]+m;d++){
            for(int j=0;j<n;j++)if(i!=j){
                if(l[j]+m<=d)continue;
                bool fp=0;
                for(int k=0;k<n;k++)if(i!=k&&j!=k&&d<l[k]){fp=1;break;}
                if(fp)continue;
                memset(f,0,sizeof(f));
                if(l[j]>d)f[0]=m,e=0;
                else f[0]=l[j]+m-d,f[1]=-1,e=1;
                for(int k=0;k<n;k++)if(i!=k&&j!=k){
                    if(l[k]+m<=d){for(int z=0;z<=e;z++)f[z]*=m;}
                    else{for(int z=e;z>=0;z--)f[z+1]+=f[z],f[z]*=(d-l[k]);e++;}
                }
                for(int z=0;z<=e;z++)an[i]+=1.0*f[z]/(z+1);
            }
        }
    }
    db P=1;for(int i=1;i<=n;i++)P*=m;
    for(db &x:an)x/=P;return an;
}
int n,n_;
const db eps=1e-12;
int pp[(1<<9)+10],lk[(1<<9)+10],sn[1010];
db dp[1010][(1<<9)+10][15],xs[(1<<9)+10][15][15],ans[1010];
int main(){
	scanf("%d%d",&n,&m);n_=m-1;
    for(int s=1;s<(1<<n_);s++)pp[s]=pp[s>>1]+(s&1),lk[s]=log2(s&-s);
    for(int s=0;s<(1<<n_);s++)for(int j=1;j<=m;j++){
        vector<int>wx;
        for(int i=n_-1;i>=0;i--)if((s>>i)&1)wx.pb(n_-1-i);
        wx.pb(n_),wx.pb(n_+j);
        vector<db>ww=sol(wx);
        int e=0;
        for(int i=n_-1;i>=0;i--)if((s>>i)&1)xs[s][j][i]=ww[e++];
        xs[s][j][n_]=ww[e++];
        xs[s][j][n_+1]=ww[e++];
    }
    for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(i>j)sn[i]|=(1<<(j-1));
    dp[n-1][sn[n-1]][1]=1;
    for(int i=n-1;i;i--)for(int s=(1<<n_)-1;s>=0;s--)for(int j=1;j<=m;j++){
        if(dp[i][s][j]<eps)continue;
        db jb=dp[i][s][j];
        int R=max(0,i-m)+pp[s]+1;
        for(int k=0;k<n_;k++)if((s>>k)&1){
            db ox=jb*xs[s][j][k];
            dp[i][s^(1<<k)][j]+=ox;
            //assert(i-1-k>0);
            ans[i-1-k]+=ox*R;
        }
        if(xs[s][j][n_]>eps){
            db ox=jb*xs[s][j][n_];
            ans[i]+=ox*R;if(R>1){
                if(!s)dp[i-m][sn[i-m]][m]+=ox;
                else{
                    int z=lk[s]+1,s2=0;
                    for(int j=1;j<=n_;j++){
                        if(i-z-j<=0)break;
                        if(z-1+j<n_){if((s>>(z-1+j))&1)s2|=(1<<(j-1));}
                        else s2|=(1<<(j-1));
                    }
                    dp[i-z][s2][min(m,z+j)]+=ox;
                }
            }
        }
        if(j<m&&xs[s][j][n_+1]>eps){
            db ox=jb*xs[s][j][n_+1];
            ans[i+j]+=ox*R;if(R>1){
                if(!s)dp[i-m][sn[i-m]][m]+=ox;
                else{
                    int z=lk[s]+1,s2=0;
                    for(int j=1;j<=n_;j++){
                        if(i-z-j<=0)break;
                        if(z-1+j<n_){if((s>>(z-1+j))&1)s2|=(1<<(j-1));}
                        else s2|=(1<<(j-1));
                    }
                    dp[i-z][s2][z]+=ox;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)printf("%.9lf\n",ans[i]+1);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2

output:

2.109375000
2.625000000
1.265625000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 65ms
memory: 66132kb

input:

1000 10

output:

2.927293246
3.537316064
4.281182083
5.131220508
6.053932593
7.019188288
8.005702141
9.001290736
10.000164877
10.999999632
11.999999596
12.999999559
13.999999522
14.999999485
15.999999449
16.999999412
17.999999375
18.999999339
19.999999302
20.999999265
21.999999229
22.999999192
23.999999155
24.999999...

result:

ok 1000 numbers

Test #3:

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

input:

300 8

output:

2.751263044
3.390073717
4.175006852
5.066021503
6.020146538
7.004557835
8.000572565
8.999999968
9.999999964
10.999999960
11.999999956
12.999999952
13.999999948
14.999999944
15.999999940
16.999999936
17.999999932
18.999999928
19.999999924
20.999999920
21.999999916
22.999999912
23.999999908
24.9999999...

result:

ok 300 numbers

Test #4:

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

input:

1000 3

output:

2.230256168
3.034765671
4.000000000
5.000000000
6.000000000
7.000000000
8.000000000
9.000000000
10.000000000
11.000000000
12.000000000
13.000000000
14.000000000
15.000000000
16.000000000
17.000000000
18.000000000
19.000000000
20.000000000
21.000000000
22.000000000
23.000000000
24.000000000
25.000000...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 25ms
memory: 6904kb

input:

7 10

output:

2.981586438
3.493604960
3.965342265
4.319677059
4.508724856
4.498880848
4.232183574

result:

ok 7 numbers

Test #6:

score: 0
Accepted
time: 23ms
memory: 38948kb

input:

993 9

output:

2.841121207
3.464359215
4.227324329
5.096942550
6.035281606
7.010574172
8.002387311
9.000302424
9.999999893
10.999999882
11.999999870
12.999999858
13.999999846
14.999999834
15.999999822
16.999999811
17.999999799
18.999999787
19.999999775
20.999999763
21.999999751
22.999999740
23.999999728
24.9999997...

result:

ok 993 numbers