QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#382163 | #8511. Greek Casino | kevinshan# | WA | 2ms | 10172kb | C++17 | 2.5kb | 2024-04-08 04:19:33 | 2024-04-08 04:19:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long double
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second
long long GCD(long long x, long long y)
{
if (y == 0) return x;
return GCD(y, x%y);
}
long long LCM(long long x, long long y)
{
return (x * y) / GCD(x, y);
}
const int MAXN = 1e5 + 5;
ll dp[MAXN];
vector<int> fac[MAXN];
vector<long long> lcms[MAXN];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen("input.in", "r")) {
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
}
int n; cin>>n;
long long ar[n+1];
int tot = 0;
for(int i=1; i<=n; i++) cin>>ar[i];
for(int i=1; i<=n; i++){
for(int j=1; j*j<=i; j++){
if(i%j == 0) {
fac[i].pb(j);
if(i/j != j) fac[i].pb(i/j);
}
}
}
for(int i=1; i<=n; i++){
for(int j:fac[i]) lcms[i].pb(LCM((long long)i,(long long)j));
}
int denom = 0;
for(int i=1; i<=n; i++) denom += ar[i];
ll res = 0;
for(int i=n; i>=1; i--){
// if(i > 1) dp[i] += 1;
int stay_same = 0;
for(int j:fac[i]) stay_same += ar[j];
// cout<<i<<"|"<<stay_same<<"/"<<denom<<"\n";
// cout<<i<<"|"<<stay_same<<"<"<<((ll)stay_same * (ll)(denom - stay_same)) / ((ll)stay_same * (ll)stay_same)<<"\n";
dp[i] += (ll)(stay_same) / ((ll)(denom-stay_same));
for(int j=2; j*i<=n; j++){
int prob = 0;
// cout<<i<<"*"<<j<<"="<<i*j<<" ";
for(int l=0; l<fac[i].size(); l++){
if(((long long)j*i)%(lcms[i][l]) == 0) {
int oth = (j*i) / (lcms[i][l]) * fac[i][l];
prob += ar[oth];
}
}
// for(int fc:fac[i]){
// if(fc % pw == 0) {
// // cout<<fc<<":"<<fc*j<<" ";
// int oth = fc * j;
// prob += ar[oth];
// }
// }
// cout<<"\n";
// cout<<i<<"<<"<<prob<<"|"<<denom<<"\n";
dp[i] += ((ll) prob / (ll) (denom - stay_same)) * (dp[j*i] + 1);
}
// dp[i] += (ll) denom / (ll) (denom - stay_same);
}
// cout<<"\n";
// cout<<"DP: ";
// for(int i=1; i<=n; i++) cout<<dp[i]<<" ";
// cout<<"\n";
cout<<fixed<<setprecision(20)<<dp[1];
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9080kb
input:
3 1 1 1
output:
3.50000000000000000000
result:
ok found '3.500000000', expected '3.500000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 9080kb
input:
3 1 1 2
output:
3.66666666666666666674
result:
ok found '3.666666667', expected '3.666666667', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 10172kb
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.02426396154343988284
result:
wrong answer 1st numbers differ - expected: '1.0183368', found: '1.0242640', error = '0.0058204'