QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#382148 | #8511. Greek Casino | kevinshan# | WA | 1ms | 6960kb | C++17 | 2.0kb | 2024-04-08 03:51:52 | 2024-04-08 03:51:52 |
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
const int MAXN = 1e5 + 5;
ll dp[MAXN];
vector<int> fac[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;
int 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);
}
}
}
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;
int pw = 1;
int pwcnt = 0;
for(int l=1; l<=20; l++) {
if(i % (pw*j) != 0) break;
pw *= j;
pwcnt = l;
}
for(int fc:fac[i]){
if(fc % pw == 0) {
int oth = fc * j;
prob += ar[oth];
}
}
// cout<<i<<"<<"<<prob<<"|"<<denom<<"\n";
dp[i] += ((ll) prob / (ll) (denom - stay_same)) * (dp[j*i]);
}
// dp[i] += (ll) denom / (ll) (denom - stay_same);
}
// cout<<"\n";
// cout<<"DP: ";
// for(int i=1; i<=n; i++) cout<<dp[i]<<" ";
cout<<fixed<<setprecision(20)<<dp[1];
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6120kb
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: 1ms
memory: 6960kb
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: 0ms
memory: 6308kb
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.02156431621844709010
result:
wrong answer 1st numbers differ - expected: '1.0183368', found: '1.0215643', error = '0.0031694'