QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#382154#8511. Greek Casinokevinshan#WA 1ms7228kbC++172.0kb2024-04-08 03:57:052024-04-08 03:57:05

Judging History

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

  • [2024-04-08 03:57:05]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7228kb
  • [2024-04-08 03:57:05]
  • 提交

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] + 1);
        }

        // 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];


    
}


详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 6832kb

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: 6188kb

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: 1ms
memory: 7228kb

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'