QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#711574 | #6565. Game Show Elimination | ucup-team902 | WA | 0ms | 3892kb | C++20 | 3.8kb | 2024-11-05 12:09:46 | 2024-11-05 12:09:46 |
Judging History
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=k;
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: 0
Wrong Answer
time: 0ms
memory: 3892kb
input:
3 2
output:
2.1250000000000 2.4843750000000 1.2656250000000
result:
wrong answer 1st numbers differ - expected: '2.1093750', found: '2.1250000', error = '0.0074074'