QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#23784#1777. Fortune From Follygalaxias#WA 3ms3784kbC++111.4kb2022-03-19 14:32:052022-04-30 04:08:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 04:08:17]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3784kb
  • [2022-03-19 14:32:05]
  • 提交

answer

#include <bits/stdc++.h>

#define db double

const db eps = 1e-6 ;
const int MAX_N = 100 + 10 ;

int n , m , k ;
bool ed[MAX_N] ;
db p , A[MAX_N][MAX_N] ;

void gauss() {
    for (int i = 0 ; i < m ; ++i) {
        for (int j = i + 1 ; j < m ; ++j)
            if (abs(A[i][i]) < abs(A[j][i])) for (int k = 0 ; k <= m ; ++k) std::swap(A[i][k] , A[j][k]) ;

        for (int j = i + 1 ; j < m ; ++j) {
            db xs = A[j][i] / A[i][i] ;
            for (int k = i ; k <= m ; ++k) A[j][k] -= xs * A[i][k] ;
        }
    }

    for (int i = m - 1 ; i >= 0 ; --i) {
        for (int j = i + 1 ; j < m ; ++j) A[i][m] -= A[j][m] * A[i][j] ;
        if (abs(A[i][i]) > eps) A[i][m] /= A[i][i] ;
        else A[i][m] = 0 ;
    }
}

int main() {
    scanf("%d %d %lf" , &n , &k , &p) ;

    m = (1 << n) ;
    for (int i = 0 ; i < m ; ++i) {
        int cnt = 0 ;
        for (int j = 0 ; j < n ; ++j) if ((1 << j) & i) ++cnt ;
        if (cnt >= k) ed[i] = 1 ;
    }
    
    for (int i = 0 ; i < m ; ++i) {
        A[i][i] = 1 ;

        for (int j = 0 ; j < 2 ; ++j) {
            int ni = (i << 1) & (m - 1) | j ;
            if (ed[ni]) continue ;

            A[i][m] = 1 ;
            if (j) A[i][ni] -= p ;
            else A[i][ni] -= 1 - p ;
        }
    }
    gauss() ;

    db res = 0 ;
    for (int i = 0 ; i < m ; ++i) if (ed[i]) res += A[i][m] ;
    printf("%0.7lf\n" , res) ;

    return 0 ;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3784kb

input:

2 1 0.0006

output:

1666.6666667

result:

ok found '1666.6666667', expected '1666.6666667', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3716kb

input:

2 1 0.0043

output:

232.5581395

result:

ok found '232.5581395', expected '232.5581395', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

2 1 0.4202

output:

2.3798191

result:

ok found '2.3798191', expected '2.3798191', error '0.0000000'

Test #4:

score: 0
Accepted
time: 3ms
memory: 3756kb

input:

2 1 0.6729

output:

1.4861049

result:

ok found '1.4861049', expected '1.4861049', error '0.0000000'

Test #5:

score: 0
Accepted
time: 3ms
memory: 3648kb

input:

2 1 0.9925

output:

1.0075567

result:

ok found '1.0075567', expected '1.0075567', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

2 1 0.9999

output:

1.0001000

result:

ok found '1.0001000', expected '1.0001000', error '0.0000000'

Test #7:

score: -100
Wrong Answer
time: 3ms
memory: 3644kb

input:

2 2 0.0006

output:

2777777.7774304

result:

wrong answer 1st numbers differ - expected: '2779444.4444444', found: '2777777.7774304', error = '0.0005996'