QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#712557 | #6565. Game Show Elimination | ucup-team902 | AC ✓ | 694ms | 89544kb | C++20 | 3.8kb | 2024-11-05 16:09:15 | 2024-11-05 16:09:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using db=long double;
const int N=1024,K=1<<9;
const db eps=1e-12;
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);
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);
}
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--){
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;
if(nd>=k)
ans[i]+=c;
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: 3940kb
input:
3 2
output:
2.1093750000000 2.6250000000000 1.2656250000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 694ms
memory: 89544kb
input:
1000 10
output:
2.9272933166112 3.5373161568760 4.2811822033069 5.1312206601865 6.0539327790165 7.0191885098663 8.0057023991095 9.0012910303480 10.0001652076757 11.0000000000000 12.0000000000000 13.0000000000000 14.0000000000000 15.0000000000000 16.0000000000000 17.0000000000000 18.0000000000000 19.0000000000000 20...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 39ms
memory: 20172kb
input:
300 8
output:
2.7512630513322 3.3900737270548 4.1750068650797 5.0660215194411 6.0201465578408 7.0045578588980 8.0005725930652 9.0000000000000 10.0000000000000 11.0000000000000 12.0000000000000 13.0000000000000 14.0000000000000 15.0000000000000 16.0000000000000 17.0000000000000 18.0000000000000 19.0000000000000 20...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 4ms
memory: 17952kb
input:
1000 3
output:
2.2302561681029 3.0347656711132 4.0000000000000 5.0000000000000 6.0000000000000 7.0000000000000 8.0000000000000 9.0000000000000 10.0000000000000 11.0000000000000 12.0000000000000 13.0000000000000 14.0000000000000 15.0000000000000 16.0000000000000 17.0000000000000 18.0000000000000 19.0000000000000 20...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 294ms
memory: 5104kb
input:
7 10
output:
2.9815864383718 3.4936049601181 3.9653422649127 4.3196770585875 4.5087248562227 4.4988808476505 4.2321835741366
result:
ok 7 numbers
Test #6:
score: 0
Accepted
time: 224ms
memory: 77292kb
input:
993 9
output:
2.8411212285174 3.4643592446426 4.2273243674465 5.0969425981705 6.0352816658084 7.0105742428138 8.0023873942439 9.0003025183896 10.0000000000000 11.0000000000000 12.0000000000000 13.0000000000000 14.0000000000000 15.0000000000000 16.0000000000000 17.0000000000000 18.0000000000000 19.0000000000000 20...
result:
ok 993 numbers