QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#23930 | #2896. Black and White | huwenbo | AC ✓ | 157ms | 16076kb | C++ | 1.2kb | 2022-03-21 18:33:45 | 2022-04-30 04:29:36 |
Judging History
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;
}
詳細信息
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'