QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235659 | #6565. Game Show Elimination | ugly2333 | AC ✓ | 192ms | 48120kb | C++20 | 2.1kb | 2023-11-02 23:34:57 | 2023-11-02 23:34:58 |
Judging History
answer
//Δ_H
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 1111;
const int K = 11;
const int W = 1<<9;
int n,k,w;
DB p[W][K][K],f[N][W][K],s[N];
void solve(int m,int t,DB*p){
int a[K],i,j,l,o,x;
DB f[K],g[K],nf[K],ng[K];
memset(a,0,sizeof(a));
a[0]=k;
for(i=1;i<k;i++)
if(m&(1<<(i-1)))
a[i]=k-i;
a[k]=k+t;
for(i=0;i<=k;i++){
if(a[i]){
for(l=a[i];l<a[i]+k;l++){
for(o=0;o<=k;o++)
f[o]=0,g[o]=0,nf[o]=0,ng[o]=0;
f[0]=(DB)1/k;
for(j=0;j<=k;j++){
if(a[j]&&j!=i){
x=max(a[j]+k-max(l+1,a[j]),0);
for(o=0;o<=k;o++)
ng[o]+=f[o]*x/k;
x=(a[j]<=l&&l+1<=a[j]+k);
for(o=1;o<=k;o++)
nf[o]+=f[o-1]*x/k,ng[o]+=g[o-1]*x/k;
x=max(min(l,a[j]+k)-a[j],0);
for(o=0;o<=k;o++)
nf[o]+=f[o]*x/k,ng[o]+=g[o]*x/k;
for(o=0;o<=k;o++)
f[o]=nf[o],g[o]=ng[o],nf[o]=0,ng[o]=0;
}
}
for(o=1;o<=k;o++)
p[i]+=f[o]/(o+1);
for(o=0;o<=k;o++)
p[i]+=g[o]/(o+1);
}
}
}//cout<<m<<' '<<t<<endl;
//for(i=0;i<=k;i++)cout<<i<<' '<<p[i]<<endl;cout<<endl;
}
int main(){
int i,j,l,o,x,y,z;
scanf("%d%d",&n,&k);
w=1<<(k-1);
for(i=0;i<w;i++)
for(j=1;j<=k;j++)
solve(i,j,p[i][j]);
x=0;
for(i=1;i<=k-1;i++)
if(n-1-i>=1)
x|=1<<(i-1);
f[n-1][x][1]=1;
for(l=n;l>=1;l--){
for(i=w-1;i>=0;i--){
for(j=1;j<=k;j++){
z=max(l-k,0)+__builtin_popcount(i)+1;//cout<<l<<' '<<i<<' '<<j<<' '<<f[l][i][j]<<endl;
for(o=1;o<=k-1;o++){
if(i&(1<<(o-1))){
f[l][i^(1<<(o-1))][j]+=f[l][i][j]*p[i][j][o];
s[l-o]+=f[l][i][j]*p[i][j][o]*z;
}
}
x=i,y=l;
while(!(x&1)&&y>=1){
y--;
x>>=1;
if(y-(k-1)>=1)
x|=1<<(k-2);
}
if(y){
y--;
x>>=1;
if(y-(k-1)>=1)
x|=1<<(k-2);
f[y][x][min(l+j-y,k)]+=f[l][i][j]*p[i][j][0];
f[y][x][min(l-y,k)]+=f[l][i][j]*p[i][j][k];
}
s[l]+=f[l][i][j]*p[i][j][0]*z;
s[l+j]+=f[l][i][j]*p[i][j][k]*z;
}
}
}
for(i=1;i<=n;i++)
printf("%.12lf\n",s[i]+1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3592kb
input:
3 2
output:
2.109375000000 2.625000000000 1.265625000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 192ms
memory: 48120kb
input:
1000 10
output:
2.927293316612 3.537316156877 4.281182203308 5.131220660188 6.053932779018 7.019188509868 8.005702399112 9.001291030351 10.000165207679 11.000000000003 12.000000000004 13.000000000004 14.000000000004 15.000000000005 16.000000000005 17.000000000005 18.000000000006 19.000000000006 20.000000000007 21.0...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 11ms
memory: 9032kb
input:
300 8
output:
2.751263051332 3.390073727055 4.175006865080 5.066021519441 6.020146557841 7.004557858898 8.000572593065 9.000000000000 10.000000000000 11.000000000000 12.000000000000 13.000000000000 14.000000000000 15.000000000000 16.000000000000 17.000000000000 18.000000000000 19.000000000000 20.000000000000 21.0...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 9664kb
input:
1000 3
output:
2.230256168103 3.034765671113 4.000000000000 5.000000000000 6.000000000000 7.000000000000 8.000000000000 9.000000000000 10.000000000000 11.000000000000 12.000000000000 13.000000000000 14.000000000000 15.000000000000 16.000000000000 17.000000000000 18.000000000000 19.000000000000 20.000000000000 21.0...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 74ms
memory: 4632kb
input:
7 10
output:
2.981586438372 3.493604960118 3.965342264913 4.319677058588 4.508724856223 4.498880847651 4.232183574137
result:
ok 7 numbers
Test #6:
score: 0
Accepted
time: 70ms
memory: 29524kb
input:
993 9
output:
2.841121228517 3.464359244642 4.227324367446 5.096942598170 6.035281665808 7.010574242813 8.002387394243 9.000302518388 9.999999999999 10.999999999998 11.999999999998 12.999999999998 13.999999999998 14.999999999998 15.999999999998 16.999999999997 17.999999999997 18.999999999997 19.999999999997 20.99...
result:
ok 993 numbers