QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87872 | #5377. $N$ 门问题 | tricyzhkx | 0 | 10ms | 3636kb | C++14 | 1.4kb | 2023-03-14 16:51:33 | 2023-03-14 16:51:35 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef vector<double> vd;
double solve(vd P)
{
int n=P.size();
if(n==2)
{
if(P[0]>P[1]) return 1;
else if(P[0]<P[1]) return 0;
else return 0.5;
}
double mx=-1;
vector<int> pos;
for(int i=0;i<n;i++)
if(P[i]>mx) pos={i},mx=P[i];
else if(P[i]==mx) pos.push_back(i);
auto calc=[&](int i)
{
double minn=1;
for(int j=1;j<n;j++)if(i!=j)
{
vd Q=P;
double t=(1-P[i])/(1-P[j]-P[i]);
for(int k=0;k<n;k++)
if(k!=i) Q[k]*=t;
Q.erase(Q.begin()+j);
minn=min(minn,solve(Q));
}
return minn;
};
int sz=pos.size();
if(P[0]<mx || sz==1) return calc(pos[0]);
else return 1./sz*calc(0)+(sz-1.)/sz*calc(pos[1]);
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b) return x=1,y=0,a;
ll g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
struct exCRT
{
ll a,m;
exCRT(ll _a=0,ll _m=0):a(_a),m(_m){}
bool merge(const exCRT &C)
{
ll x,y,g=exgcd(m,C.m,x,y);
if((a-C.a)%g) return false;
m=m/g*C.m;
a=(C.a+((a-C.a)/g*(lll)y%m+m)*C.m)%m;
return true;
}
}C(0,1);
int main()
{
int T;
ll a,m,n;
cin>>T;
while(T--)
{
scanf("%lld%lld",&a,&m);
if(!C.merge(exCRT(a,m))) return puts("error"),0;
}
n=C.a;
if(n>10) return puts("0.000000"),0;
vd P(n,1./n);
printf("%.6lf\n",solve(P));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 5
Accepted
time: 2ms
memory: 3532kb
input:
1 2 3
output:
0.500000
result:
ok single line: '0.500000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
1 3 5
output:
0.666667
result:
ok single line: '0.666667'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
1 4 5
output:
0.625000
result:
ok single line: '0.625000'
Test #4:
score: -5
Runtime Error
input:
1 0 4
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 2ms
memory: 3636kb
input:
8 1 160005726539569 1 233 0 1 1 2947295521 1 686719856393 1 54289 1 12649337 1 37281334283719577
output:
1.000000
result:
wrong answer 1st lines differ - expected: 'error', found: '1.000000'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Runtime Error
Test #57:
score: 25
Accepted
time: 0ms
memory: 3348kb
input:
15 15 17 2 3 5 31 4 5 12 29 38 41 3 11 44 47 16 23 11 19 6 13 3 37 1 2 21 43 5 7
output:
0.000000
result:
ok single line: '0.000000'
Test #58:
score: 0
Accepted
time: 0ms
memory: 3336kb
input:
14 10 16 21 37 0 23 0 5 11 17 1 3 17 29 19 31 33 43 6 13 4 7 16 41 9 19 0 11
output:
0.000000
result:
ok single line: '0.000000'
Test #59:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
14 7 23 2 16 2 19 9 11 2 5 7 13 2 7 25 41 25 31 3 9 7 43 3 37 8 17 9 29
output:
0.000000
result:
ok single line: '0.000000'
Test #60:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
14 2 13 14 19 38 43 10 17 3 8 21 29 0 9 4 7 2 5 1 37 2 11 5 23 22 31 10 41
output:
0.000000
result:
ok single line: '0.000000'
Test #61:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
2 543380932 999999999 451172165 1000000000
output:
0.000000
result:
ok single line: '0.000000'
Test #62:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
15 1 2 9 13 31 37 1 17 0 23 1 3 2 5 17 31 9 11 5 29 4 47 6 7 40 41 1 19 26 43
output:
0.000000
result:
ok single line: '0.000000'
Test #63:
score: 0
Accepted
time: 10ms
memory: 3336kb
input:
50000 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
output:
0.000000
result:
ok single line: '0.000000'
Test #64:
score: 0
Accepted
time: 9ms
memory: 3316kb
input:
50000 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
output:
0.000000
result:
ok single line: '0.000000'
Test #65:
score: -25
Runtime Error
input:
50000 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
0%