QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#507993#3204. Risky LotteryWorldFinalEscapedAC ✓1962ms4704kbC++202.3kb2024-08-07 01:44:412024-08-07 01:44:41

Judging History

This is the latest submission verdict.

  • [2024-08-07 01:44:41]
  • Judged
  • Verdict: AC
  • Time: 1962ms
  • Memory: 4704kb
  • [2024-08-07 01:44:41]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-5;

double best[15], bestans;
double p[15];
int n, m;
int pw3[15], go[6561][9];

double coef[8];

double calc() {
    static double dp[8][6561];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < pw3[m]; j++)
            dp[i][j] = 0;
    }
    
    dp[0][0] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < pw3[m]; j++) {
//            if (dp[i - 1][j] < eps) continue;
            for (int k = 0; k < m; k++) {
//                printf("%d -> %d\n", j, go[j][k]);
                dp[i][go[j][k]] += dp[i - 1][j] * p[k];
            }
        }
//        for (int j = 0; j < pw3[m]; j++) {
//            printf("dp[%d][%d] = %.3f\n", i, j, dp[i][j]);
//        }
    }
    double ans = 0;
    for (int k = 0; k < m; k++) {
        // ans = 0;
        coef[k] = 0;
        for (int i = 0; i < pw3[m]; i++) {
            bool ok = true;
            for (int t = 0; t < k; t++)
                if ((i / pw3[t]) % 3 == 1)
                    ok = false;
            if ((i / pw3[k]) % 3) ok = false;
            if (ok) {
                coef[k] += dp[n - 1][i];
                // ans += p[k] * dp[n - 1][i];
            }
        }
        // printf("%.10f\n", ans);
    }
    return ans;
}

mt19937 rng(114514);

const int MAGIC = 32768;
inline double rnd() {
    return (rng() & (MAGIC - 1)) / 1. / MAGIC;
}

int main() {
    cin >> n >> m;
    pw3[0] = 1;
    for (int i = 1; i <= m; i++) pw3[i] = 3 * pw3[i - 1];
    for (int i = 0; i < pw3[m]; i++) {
        for (int j = 0; j < m; j++) {
            int cur = i / pw3[j] % 3;
            if (cur == 2)
                go[i][j] = i;
            else
                go[i][j] = i + pw3[j];
        }
    }

    for (int i = 0; i < m; i++) p[i] = 1. / m;

    // p[0] = 0.46410, p[1] = 0.26795, p[2] = 0.26795, p[3] = 0;
    // printf("%.10f\n", calc());    
    // return 0;

    int times = 3000;
    while (times--) {
        calc();
        double all = 0;
        for (int i = 0; i < m; i++) {
            p[i] *= exp(coef[i]);
            all += p[i];
        }
        for (int i = 0; i < m; i++)
            p[i] /= all;
    }
    for (int i = 0; i < m; i++)
        printf("%.5f\n", p[i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 1

output:

1.00000

result:

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

Test #2:

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

input:

3 2

output:

0.50000
0.50000

result:

ok 2 numbers

Test #3:

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

input:

3 3

output:

0.46410
0.26795
0.26795

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 6ms
memory: 4084kb

input:

3 4

output:

0.45778
0.25164
0.14529
0.14529

result:

ok 4 numbers

Test #5:

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

input:

4 1

output:

1.00000

result:

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

Test #6:

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

input:

4 2

output:

0.50000
0.50000

result:

ok 2 numbers

Test #7:

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

input:

4 3

output:

0.44852
0.42633
0.12515

result:

ok 3 numbers

Test #8:

score: 0
Accepted
time: 7ms
memory: 4040kb

input:

4 4

output:

0.44773
0.42487
0.12566
0.00174

result:

ok 4 numbers

Test #9:

score: 0
Accepted
time: 28ms
memory: 4176kb

input:

4 5

output:

0.44766
0.42474
0.12570
0.00175
0.00015

result:

ok 5 numbers

Test #10:

score: 0
Accepted
time: 4ms
memory: 4032kb

input:

5 4

output:

0.36157
0.32120
0.19955
0.11767

result:

ok 4 numbers

Test #11:

score: 0
Accepted
time: 31ms
memory: 4112kb

input:

5 5

output:

0.35819
0.31559
0.19182
0.09677
0.03763

result:

ok 5 numbers

Test #12:

score: 0
Accepted
time: 120ms
memory: 4068kb

input:

5 6

output:

0.35785
0.31502
0.19107
0.09511
0.03515
0.00580

result:

ok 6 numbers

Test #13:

score: 0
Accepted
time: 33ms
memory: 4120kb

input:

6 5

output:

0.32664
0.29758
0.23155
0.12260
0.02163

result:

ok 5 numbers

Test #14:

score: 0
Accepted
time: 128ms
memory: 4208kb

input:

6 6

output:

0.32653
0.29742
0.23128
0.12245
0.02165
0.00067

result:

ok 6 numbers

Test #15:

score: 0
Accepted
time: 497ms
memory: 4280kb

input:

6 7

output:

0.32652
0.29739
0.23123
0.12242
0.02166
0.00067
0.00012

result:

ok 7 numbers

Test #16:

score: 0
Accepted
time: 529ms
memory: 4236kb

input:

7 7

output:

0.29455
0.27044
0.22469
0.14066
0.05801
0.01094
0.00072

result:

ok 7 numbers

Test #17:

score: 0
Accepted
time: 1962ms
memory: 4704kb

input:

7 8

output:

0.29453
0.27042
0.22465
0.14063
0.05797
0.01091
0.00072
0.00017

result:

ok 8 numbers