Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
73230335 Practice:
little_sun
605E - 39 GNU C++11 Accepted 187 ms 8024 KB 2020-03-14 17:43:31 2020-03-14 17:44:55
→ Source
#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const int MaxN = 1e3 + 10;

int n, vis[MaxN], a[MaxN];
double p[MaxN][MaxN], d[MaxN], sum[MaxN], pr[MaxN];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int now = 0;
        sum[i] = pr[i] = 1.0;
        for (int j = 1; j <= n; j++)
            scanf("%d", &now), p[i][j] = now * 0.01L;
    }
    vis[n] = 1, a[1] = n, d[0] = 1e18;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (vis[j]) continue;
            sum[j] += d[a[i - 1]] * p[j][a[i - 1]] * pr[j];
            pr[j] *= (1 - p[j][a[i - 1]]), d[j] = sum[j] / (1 - pr[j]);
        }
        int pos = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && d[pos] > d[j])
                pos = j;
        vis[pos] = 1, a[i] = pos;
    }
    printf("%.10lf\n", d[1]);
    std::cerr << "tiger0132 /qq";
    return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details