QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#711532 | #6565. Game Show Elimination | ucup-team902 | WA | 148ms | 15220kb | C++20 | 4.3kb | 2024-11-05 11:52:57 | 2024-11-05 11:52:58 |
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);
// if(i==1&&s==1){
// printf("%d %d %d %lf\n",i,s,j,g[i][s][j]);
// }
g[i][s][j]+=work(i,s,j,k);
// if(i==1&&s==1){
// printf("%d %d %d %lf\n",i,s,j,g[i][s][j]);
// }
g[i][s][j]+=work(i,s,j,k+1);
// if(i==1&&s==1){
// printf("%d %d %d %lf\n",i,s,j,g[i][s][j]);
// }
}
}
}
}
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);
// printf("%d %d %d %lf\n",i,j,s,f[i][j][s]);
// printf("%d %d %d %d\n",i,j,s,crk);
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);
while(1){
if(ns&1){
ns>>=1;
break;
}
ni--;
ns=(ns>>1)|(1<<k);
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3888kb
input:
3 2
output:
2.1093750000000 2.6250000000000 1.2656250000000
result:
ok 3 numbers
Test #2:
score: -100
Wrong Answer
time: 148ms
memory: 15220kb
input:
1000 10
output:
1.6337777249909 1.8498476943878 2.1194353886430 2.4355825624524 2.7908622536682 3.1794787362339 3.5988404009317 4.0492873538501 4.5322323145456 5.0481135064904 5.6700220116298 6.2919305167691 6.9138390219085 7.5357475270478 8.1576560321872 8.7795645373265 9.4014730424659 10.0233815476052 10.64529005...
result:
wrong answer 1st numbers differ - expected: '2.9272933', found: '1.6337777', error = '0.4418811'