Submission #3942773


Source Code Expand

Copy
#ifndef BZ
#pragma GCC optimize "-Ofast"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;

using namespace std;

const int MX = 307;

ld f[MX + 5][MX + 5][MX + 5];

int main() {
#ifdef FASTIO
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
    int n;
    cin >> n;
    int c1 = 0, c2 = 0, c3 = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x == 1) {
            c1++;
        } else if (x == 2) {
            c2++;
        } else {
            c3++;
        }
    }

    for (int k = 0; k < MX; k++) {
        for (int j = 0; j + k < MX; j++) {
            for (int i = 0; i + j + k < MX; i++) {
                if (i == 0 && j == 0 && k == 0) {
                    continue;
                }
                if (i + j + k > MX) {
                    continue;
                }
                ld wait = 1.0 * n / (i + j + k);
                ld pi = 1.0 * i / (i + j + k);
                ld pj = 1.0 * j / (i + j + k);
                ld pk = 1.0 * k / (i + j + k);

                if (i) {
                    f[i][j][k] += pi * f[i - 1][j][k];
                }
                if (j) {
                    f[i][j][k] += pj * f[i + 1][j - 1][k];
                }
                if (k) {
                    f[i][j][k] += pk * f[i][j + 1][k - 1];
                }
                f[i][j][k] += wait;
            }
        }
    }

    cout.precision(10);
    cout << fixed << f[c1][c2][c3] << "\n";
    return 0;
}

Submission Info

Submission Time
Task J - Sushi
User gritukan
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1791 Byte
Status
Exec Time 105 ms
Memory 233728 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17
Case Name Status Exec Time Memory
0_00 105 ms 233728 KB
0_01 105 ms 233728 KB
0_02 105 ms 233728 KB
0_03 105 ms 233728 KB
1_00 105 ms 233728 KB
1_01 105 ms 233728 KB
1_02 105 ms 233728 KB
1_03 105 ms 233728 KB
1_04 105 ms 233728 KB
1_05 105 ms 233728 KB
1_06 105 ms 233728 KB
1_07 105 ms 233728 KB
1_08 105 ms 233728 KB
1_09 105 ms 233728 KB
1_10 105 ms 233728 KB
1_11 105 ms 233728 KB
1_12 105 ms 233728 KB
1_13 105 ms 233728 KB
1_14 105 ms 233728 KB
1_15 105 ms 233728 KB
1_16 105 ms 233728 KB
1_17 105 ms 233728 KB