QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#371424 | #8511. Greek Casino | Mo_Han136# | WA | 1ms | 3980kb | C++20 | 1.2kb | 2024-03-30 11:28:47 | 2024-03-30 11:28:48 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define db double
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
using namespace std;
const int M=1e5+5,inf=1e9;
int n,w[M];
LL sum;
db p[M],E[M],Px[M];
vector<int> G[M];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void solve(int x,int g){
int z=x/g;
rep(i,0,G[z].size()-1){
int k=G[z][i];
int u=k*g,v=z/k*g;
if(u!=x)E[u]+=p[v]*(E[x]+1)/(1-Px[u]);
if(v!=x)E[v]+=p[u]*(E[x]+1)/(1-Px[v]);
}
}
void init(){
rep(z,1,n)rep(k,1,sqrt(z))if(z%k==0 && gcd(k,z/k)==1)G[z].pb(k);
}
int main(){
scanf("%d",&n);init();
rep(i,1,n)scanf("%d",&w[i]),sum+=w[i];
rep(i,1,n)p[i]=1.0*w[i]/sum;
rep(x,1,n){
rep(i,1,sqrt(x))if(x%i==0){
Px[x]+=p[i];
if(x/i!=i)Px[x]+=p[x/i];
}
E[x]+=Px[x]/(1-Px[x]);
}
drep(i,n,1){
rep(j,1,sqrt(i))if(i%j==0){
solve(i,j);
if(i/j!=i)solve(i,i/j);
}
// printf("%d :%.10lf %.10lf\n",i,Px[i],E[i]);
}
printf("%.10lf\n",E[1]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3872kb
input:
3 1 1 1
output:
3.5000000000
result:
ok found '3.500000000', expected '3.500000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
3 1 1 2
output:
3.6666666667
result:
ok found '3.666666667', expected '3.666666667', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3980kb
input:
1337 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
1.0183798349
result:
wrong answer 1st numbers differ - expected: '1.0183368', found: '1.0183798', error = '0.0000422'