QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#468627#3400. 重建little_sun100 ✓1ms4048kbC++141.7kb2024-07-08 21:53:452024-07-08 21:53:45

Judging History

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

  • [2024-07-08 21:53:45]
  • 评测
  • 测评结果:100
  • 用时:1ms
  • 内存:4048kb
  • [2024-07-08 21:53:45]
  • 提交

answer

#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
#define meow(cat...) fprintf(stderr, cat)

const double eps = 1e-7;

int n; 
double a[100][100], f[100][100];
double d[100][100], g[100][100];

int check(double x)
{
    if(x > eps) return 1;
    else if(x < -eps) return -1;
    else return 0;
}

double solve()
{
    double res = 1.0;
    // for(int i = 1; i < n; i++)
    //     for(int j = 1; j < n; j++)
    //         printf("%lf%c", a[i][j], " \n"[j == n - 1]);
    for(int i = 1; i < n; i++)
        for(int j = i + 1; j < n; j++)
        {
            while(check(a[i][i]))
            {
                double rate = a[j][i] / a[i][i];
                for(int k = i; k < n; k++)
                    a[j][k] -= rate * a[i][k];
                std::swap(a[i], a[j]), res = -res;
            }
            std::swap(a[i], a[j]), res = -res;
        }
    for(int i = 1; i < n; i++)
        res = res * a[i][i];
    return res;
}

signed main()
{   
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            scanf("%lf", &f[i][j]); 
            if(check(f[i][j] - 1.0) == 0) f[i][j] = 1.0 - eps;
            else if(check(f[i][j]) == 0) f[i][j] = eps;
            double r = f[i][j] / (1.0 - f[i][j]); 
            if(i <= j) continue;
            g[i][j] = g[j][i] = r, d[i][i] += r, d[j][j] += r;
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            a[i][j] = d[i][j] - g[i][j];
    double ans = solve();
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            ans *= (1.0 - f[i][j]);
    printf("%lf\n", ans);
    return 0;
}

详细

Test #1:

score: 10
Accepted
time: 0ms
memory: 3892kb

input:

10
0.00 0.00 0.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 1.00 0.00 1.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 0.00 1.00
1.00 1.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0....

output:

0.999996

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #2:

score: 10
Accepted
time: 0ms
memory: 3936kb

input:

8
0.0 1.0 0.25 0.875 0.0 0.25 1.0 0.25
1.0 0.0 0.0 0.25 0.0 0.0 0.0 0.25
0.25 0.0 0.0 0.0 0.0 0.875 0.125 0.0
0.875 0.25 0.0 0.0 0.0 0.125 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0
0.25 0.0 0.875 0.125 0.0 0.0 1.0 1.0
1.0 0.0 0.125 0.0 1.0 1.0 0.0 0.125
0.25 0.25 0.0 0.0 0.0 1.0 0.125 0.0 0.0 0.0

output:

0.138839

result:

ok found '0.13884', expected '0.13884', error '0.00000'

Test #3:

score: 10
Accepted
time: 0ms
memory: 3976kb

input:

7
0.0 1.0 0.0 1.0 0.0 1.0 0.0
1.0 0.0 0.375 0.25 0.0 0.0 1.0
0.0 0.375 0.0 0.25 0.0 1.0 0.125
1.0 0.25 0.25 0.0 0.75 0.125 0.0
0.0 0.0 0.0 0.75 0.0 0.0 0.0
1.0 0.0 1.0 0.125 0.0 0.0 0.0
0.0 1.0 0.125 0.0 0.0 0.0 0.0 0.0 0.0

output:

0.201874

result:

ok found '0.20187', expected '0.20187', error '0.00000'

Test #4:

score: 10
Accepted
time: 0ms
memory: 3888kb

input:

10
0.00 0.02 1.00 0.03 0.03 0.80 0.03 0.03 0.80 0.90
0.02 0.00 0.02 0.02 0.04 0.90 0.04 0.01 0.04 0.02
1.00 0.02 0.00 0.02 0.80 0.35 0.80 1.00 0.02 0.01
0.03 0.02 0.02 0.00 0.04 1.00 0.01 0.90 0.02 0.01
0.03 0.04 0.80 0.04 0.00 0.02 0.90 0.03 1.00 0.35
0.80 0.90 0.35 1.00 0.02 0.00 0.03 0.02 0.03 0....

output:

0.006078

result:

ok found '0.00608', expected '0.00608', error '0.00000'

Test #5:

score: 10
Accepted
time: 0ms
memory: 3940kb

input:

12
0.00 0.02 0.30 0.20 0.30 0.20 0.21 0.21 0.20 0.21 0.30 0.65
0.02 0.00 0.20 0.60 1.00 0.20 0.20 0.21 0.20 0.30 0.02 0.30
0.30 0.20 0.00 0.20 0.02 0.60 0.20 0.02 0.65 0.20 0.21 0.02
0.20 0.60 0.20 0.00 0.20 0.20 0.20 0.30 0.65 0.60 0.02 0.21
0.30 1.00 0.02 0.20 0.00 0.21 0.30 1.00 0.20 0.60 0.21 0....

output:

0.000137

result:

ok found '0.00014', expected '0.00014', error '0.00000'

Test #6:

score: 10
Accepted
time: 0ms
memory: 4000kb

input:

16
0.0 0.25 0.0 0.0 1.0 0.75 0.0 0.0 1.0 0.125 0.0 0.25 0.0 0.0 0.25 0.0
0.25 0.0 0.0 0.0 0.0 0.125 0.0 0.0 0.0 0.125 0.875 0.0 0.0 0.0 1.0 0.0
0.0 0.0 0.0 0.0 0.25 0.125 0.375 1.0 0.0 0.375 0.25 0.0 1.0 0.25 0.0 0.125
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.25 0.0 1.0 0.0 0.0 0.0 0.0 0.0
1.0 0.0 0.25 0.0...

output:

0.000100

result:

ok found '0.00010', expected '0.00010', error '0.00000'

Test #7:

score: 10
Accepted
time: 0ms
memory: 3956kb

input:

16
0.00 0.07 0.07 0.10 0.18 0.10 0.02 0.10 0.15 0.10 0.18 0.15 1.00 0.02 0.18 0.15
0.07 0.00 0.87 0.65 0.07 0.07 0.10 0.02 0.07 0.15 0.02 0.15 0.10 0.18 0.90 0.02
0.07 0.87 0.00 0.10 0.07 0.07 0.15 0.07 0.02 0.10 0.02 0.65 0.07 0.65 0.02 0.07
0.10 0.65 0.10 0.00 0.10 0.02 0.10 0.07 0.15 0.02 0.18 0....

output:

0.000146

result:

ok found '0.00015', expected '0.00015', error '0.00000'

Test #8:

score: 10
Accepted
time: 1ms
memory: 4048kb

input:

45
0.00 0.00 0.00 0.00 0.00 0.00 0.02 0.01 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.02 0.00 0.00 0.00 0.00 0.00 0.02 0.00 0.00 0.00 0.00 0.00 0.98 0.00 0.01 0.00 0.00 0.00 0.00 0.00 0.02 0.02 0.00 0.00 0.00 0.01 0.02 0.00 0.02 0.90
0.00 0.00 0.00 0.00 0.00 0.01 0.01 0.01 0.01 0.01 0.02 0.00 0.00 0.00 0....

output:

0.000238

result:

ok found '0.00024', expected '0.00024', error '0.00000'

Test #9:

score: 10
Accepted
time: 1ms
memory: 4036kb

input:

40
0.00 0.00 0.02 0.01 0.00 0.00 0.02 0.00 0.00 0.00 0.02 0.01 0.00 0.01 0.00 0.95 0.00 0.02 0.01 0.00 0.90 0.01 0.01 0.02 0.00 0.00 0.00 0.00 0.00 0.01 0.00 0.00 0.00 0.01 0.01 0.02 0.00 0.00 0.02 0.00
0.00 0.00 0.00 0.00 0.00 0.01 0.00 0.01 0.00 0.00 0.00 0.00 0.02 0.00 0.01 0.01 0.00 0.02 0.00 0....

output:

0.000333

result:

ok found '0.00033', expected '0.00033', error '0.00000'

Test #10:

score: 10
Accepted
time: 1ms
memory: 3936kb

input:

45
0.00 0.90 0.00 0.02 0.00 0.00 0.00 0.02 0.01 0.90 0.96 0.00 0.00 0.00 0.00 0.00 0.02 0.01 0.00 0.00 0.02 0.00 0.01 0.00 0.02 0.00 0.00 0.00 0.00 0.00 0.01 0.00 0.00 0.00 0.90 0.00 0.00 0.00 0.98 0.00 0.01 0.00 0.02 0.00 0.00
0.90 0.00 0.00 0.00 0.00 0.00 0.02 0.00 0.00 0.00 0.01 0.02 0.00 0.00 0....

output:

0.000108

result:

ok found '0.00011', expected '0.00011', error '0.00000'