QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#23930#2896. Black and WhitehuwenboAC ✓157ms16076kbC++1.2kb2022-03-21 18:33:452022-04-30 04:29:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 04:29:36]
  • 评测
  • 测评结果:AC
  • 用时:157ms
  • 内存:16076kb
  • [2022-03-21 18:33:45]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,S,bit[1<<20];
double f[25],dp[1<<20],F[25][2],G[25][2],p,q;

ll read(){
    ll x=0,w=0;char ch=getchar();
    while(!isdigit(ch)) w|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return w?-x:x;
}

void print(ll x){
	if(x>=10) print(x/10);
	putchar(x%10+'0');
}

int main(){
	n=read();
	for(int i=1;i<=n;i++) scanf("%lf",&f[i]);
	S=1<<n;
	for(int i=1;i<S;i++) bit[i]=bit[i/2]+(i&1);
	for(int i=1;i<S;i++){
		if(bit[i]==1) continue;
		if(bit[i]==2) dp[i]=0;
		else{
			F[0][0]=F[0][1]=1;
			for(int j=1;j<=n;j++){
				F[j][0]=F[j-1][0];
				F[j][1]=F[j-1][1];
				if(i&(1<<(j-1))) F[j][0]*=f[j],F[j][1]*=1-f[j];
			}
			G[n+1][0]=G[n+1][1]=1;
			for(int j=n;j>=1;j--){
				G[j][0]=G[j+1][0];
				G[j][1]=G[j+1][1];
				if(i&(1<<(j-1))) G[j][0]*=f[j],G[j][1]*=1-f[j];
			}
			q=1;
			for(int j=1;j<=n;j++){
				if(i&(1<<(j-1))){
					p=F[j-1][0]*G[j+1][0]*(1-f[j])+F[j-1][1]*G[j+1][1]*f[j];
					dp[i]+=p*(dp[i^(1<<(j-1))]+1);
					q-=p;
				}
			}
			dp[i]+=q;
			dp[i]/=1-q;
		}
	}
	printf("%.7lf\n",dp[S-1]);
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5696kb

input:

2
0.616
0.689

output:

0.0000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #2:

score: 0
Accepted
time: 156ms
memory: 16048kb

input:

20
0.256
0.546
0.617
0.86
0.138
0.282
0.271
0.124
0.238
0.769
0.899
0.214
0.166
0.626
0.876
0.161
0.774
0.891
0.819
0.653

output:

1393404.7887560

result:

ok found '1393404.7887560', expected '1393404.7887950', error '0.0000000'

Test #3:

score: 0
Accepted
time: 4ms
memory: 5760kb

input:

3
0.883
0.132
0.135

output:

1.1155498

result:

ok found '1.1155498', expected '1.1155498', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 6116kb

input:

15
0.739
0.448
0.842
0.564
0.457
0.406
0.767
0.769
0.357
0.852
0.721
0.826
0.228
0.122
0.512

output:

1845.8272349

result:

ok found '1845.8272349', expected '1845.8272349', error '0.0000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 5932kb

input:

14
0.521
0.652
0.578
0.388
0.81
0.813
0.477
0.829
0.491
0.716
0.288
0.383
0.758
0.848

output:

388.9970662

result:

ok found '388.9970662', expected '388.9970662', error '0.0000000'

Test #6:

score: 0
Accepted
time: 18ms
memory: 6860kb

input:

17
0.209
0.155
0.691
0.87
0.145
0.102
0.332
0.487
0.685
0.478
0.675
0.315
0.661
0.116
0.257
0.801
0.495

output:

11037.9445409

result:

ok found '11037.9445409', expected '11037.9445409', error '0.0000000'

Test #7:

score: 0
Accepted
time: 4ms
memory: 5912kb

input:

7
0.539
0.175
0.778
0.453
0.391
0.516
0.518

output:

23.1793180

result:

ok found '23.1793180', expected '23.1793180', error '0.0000000'

Test #8:

score: 0
Accepted
time: 5ms
memory: 5956kb

input:

14
0.49
0.211
0.349
0.33
0.43
0.71
0.577
0.238
0.521
0.613
0.528
0.63
0.4
0.294

output:

1102.8643059

result:

ok found '1102.8643059', expected '1102.8643059', error '0.0000000'

Test #9:

score: 0
Accepted
time: 13ms
memory: 6336kb

input:

16
0.564
0.338
0.674
0.81
0.12
0.171
0.692
0.455
0.423
0.297
0.773
0.178
0.428
0.822
0.471
0.506

output:

12659.1052855

result:

ok found '12659.1052855', expected '12659.1052855', error '0.0000000'

Test #10:

score: 0
Accepted
time: 1ms
memory: 5872kb

input:

12
0.236
0.652
0.797
0.853
0.377
0.48
0.445
0.127
0.231
0.893
0.26
0.334

output:

960.9267330

result:

ok found '960.9267330', expected '960.9267330', error '0.0000000'

Test #11:

score: 0
Accepted
time: 8ms
memory: 6068kb

input:

15
0.441
0.114
0.363
0.838
0.408
0.147
0.156
0.324
0.37
0.797
0.539
0.143
0.465
0.491
0.413

output:

912.5201799

result:

ok found '912.5201799', expected '912.5201799', error '0.0000000'

Test #12:

score: 0
Accepted
time: 8ms
memory: 6036kb

input:

15
0.415
0.35
0.648
0.155
0.183
0.297
0.828
0.771
0.703
0.196
0.178
0.633
0.859
0.293
0.505

output:

6347.3844128

result:

ok found '6347.3844128', expected '6347.3844128', error '0.0000000'

Test #13:

score: 0
Accepted
time: 155ms
memory: 16076kb

input:

20
0.285
0.478
0.189
0.427
0.711
0.68
0.765
0.302
0.383
0.313
0.5
0.849
0.318
0.406
0.157
0.498
0.709
0.526
0.314
0.507

output:

92303.2113847

result:

ok found '92303.2113847', expected '92303.2113846', error '0.0000000'

Test #14:

score: 0
Accepted
time: 157ms
memory: 16076kb

input:

20
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.5
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9

output:

74234415.9981081

result:

ok found '74234415.9981081', expected '74234415.6743832', error '0.0000000'

Test #15:

score: 0
Accepted
time: 157ms
memory: 16020kb

input:

20
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9
0.9

output:

194776970.4545985

result:

ok found '194776970.4545985', expected '194776950.7616470', error '0.0000001'