QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235659#6565. Game Show Eliminationugly2333AC ✓192ms48120kbC++202.1kb2023-11-02 23:34:572023-11-02 23:34:58

Judging History

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

  • [2023-11-02 23:34:58]
  • 评测
  • 测评结果:AC
  • 用时:192ms
  • 内存:48120kb
  • [2023-11-02 23:34:57]
  • 提交

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