QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#367951 | #8511. Greek Casino | ucup-team1196# | WA | 2ms | 4104kb | C++23 | 1.3kb | 2024-03-26 17:39:30 | 2024-03-26 17:39:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
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){
for(int j=i+i;j<=n;j+=i){
int ans=0;
for(auto v:fac[i]){
if(__gcd(i/v,j/i)==1) ans+=a[j/i*v];
}
sum[i].push_back(ans);
}
}
for(int i=n;i;--i){
double p=self[i]*1.0l/tot;
f[i]=0;
double ans=p;
int cnt=0;
for(int j=i+i;j<=n;j+=i){
ans+=(f[j]+1)*(sum[i][cnt++]*1.0l/tot);
}
f[i]=1./(1-p)*ans;
}
cout<<setprecision(20)<<f[1]<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
input:
3 1 1 1
output:
3.5000000000000000004
result:
ok found '3.500000000', expected '3.500000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
3 1 1 2
output:
3.6666666666666666667
result:
ok found '3.666666667', expected '3.666666667', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 4104kb
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.0258818654903283251
result:
wrong answer 1st numbers differ - expected: '1.0183368', found: '1.0258819', error = '0.0074092'