QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#367945 | #8511. Greek Casino | ucup-team1196# | WA | 3ms | 4100kb | C++23 | 1.3kb | 2024-03-26 17:28:29 | 2024-03-26 17:28:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
vector<int>a(n+1);
vector<double>f(n+1);
vector<int>self(n+1),st(n+1),p;
vector<vector<int>>fac(n+1);
int tot=0;
for(int i=1;i<=n;++i) cin>>a[i],tot+=a[i];
st[1]=1;
for(int i=1;i<=n;++i){
for(int j=i;j<=n;j+=i) self[j]+=a[i];
if(!st[i]){
p.push_back(i);
for(int j=2*i;j<=n;j+=i) st[i]=1;
}
for(int j=1;j*j<=n;++j){
if(i%j) continue;
fac[i].push_back(j);
if(i/j!=j) fac[i].push_back(i/j);
}
}
vector<vector<int>>sum(n+1);
for(int i=1;i<=n;++i){
int ans=0;
for(int j=i+i;j<=n;j+=i){
for(auto v:fac[j]){
if(__gcd(j/v,j/i)==1) ans+=a[v];
}
sum[i].push_back(ans);
}
}
for(int i=n;i;--i){
double p=self[i]*1./tot;
f[i]=p/(1-p);
double ans=0;
int cnt=0;
for(int j=i+i;j<=n;j+=i){
ans+=f[j]*(sum[i][cnt++]*1./tot);
}
f[i]+=1./(1-p)*ans;
}
cout<<setprecision(15)<<f[1]<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3748kb
input:
3 1 1 1
output:
3.5
result:
ok found '3.500000000', expected '3.500000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
3 1 1 2
output:
3.66666666666667
result:
ok found '3.666666667', expected '3.666666667', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 3ms
memory: 4100kb
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:
4.31210540186558
result:
wrong answer 1st numbers differ - expected: '1.0183368', found: '4.3121054', error = '3.2344589'