QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#371424#8511. Greek CasinoMo_Han136#WA 1ms3980kbC++201.2kb2024-03-30 11:28:472024-03-30 11:28:48

Judging History

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

  • [2024-03-30 11:28:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3980kb
  • [2024-03-30 11:28:47]
  • 提交

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'