Submission #3976565


Source Code Expand

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    int N;
    vector<int> C;


    void input() {
        cin >> N;
        C.resize(N);
        rep(i, 0, N) cin >> C[i];

    }

    double calc(int c) {
        double ret = 0.0;
        int k = 0;
        vector<int> D;
        for (int i = 0; i < N; ++i) {
            if (i != c) D.push_back(C[i]);

            if (i != c && C[c] % C[i] == 0) {
                k++;
            }
        }

        vector<vector<double> > dp(N, vector<double>(N, 0.0));
        dp[0][0] = 1.0;

        for (int i = 0; i < N - 1; ++i) {
            for (int j = 0; j < N - 1; ++j) {
                int nokori = N - 1 - i;

                //例のアレを置かない
                dp[i + 1][j] += dp[i][j] * (N - 1 - k - (i - j)) / (nokori);

                //例のアレを置く
                dp[i + 1][j + 1] += dp[i][j] * (k - j) / (nokori);
            }
        }

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; j += 2) {
                ret += dp[i][j];
            }
        }

        ret /= N;

        return ret;
    }

    void solve() {
        input();

        double ans = 0.0;
        for (int i = 0; i < N; ++i) {
            double tmp = 0.0;
            tmp = calc(i);
            ans += tmp;
        }

        cout << fixed << setprecision(9);
        cout << ans << endl;

    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    Solve().solve();


    return 0;
}

Submission Info

Submission Time
Task C - コイン
User homesentinel
Language C++14 (Clang 3.8.0)
Score 100
Code Size 2724 Byte
Status AC
Exec Time 8 ms
Memory 504 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 99 / 99 1 / 1
Status
AC × 3
AC × 20
AC × 40
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt
Subtask2 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt
Case Name Status Exec Time Memory
sample_01.txt AC 6 ms 504 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 1 ms 256 KB
subtask1_12.txt AC 1 ms 256 KB
subtask1_13.txt AC 1 ms 256 KB
subtask1_14.txt AC 1 ms 256 KB
subtask1_15.txt AC 1 ms 256 KB
subtask1_16.txt AC 1 ms 256 KB
subtask1_17.txt AC 1 ms 256 KB
subtask1_18.txt AC 1 ms 256 KB
subtask1_19.txt AC 1 ms 256 KB
subtask1_20.txt AC 1 ms 256 KB
subtask2_01.txt AC 1 ms 256 KB
subtask2_02.txt AC 1 ms 256 KB
subtask2_03.txt AC 1 ms 256 KB
subtask2_04.txt AC 2 ms 256 KB
subtask2_05.txt AC 8 ms 384 KB
subtask2_06.txt AC 5 ms 256 KB
subtask2_07.txt AC 4 ms 256 KB
subtask2_08.txt AC 8 ms 384 KB
subtask2_09.txt AC 8 ms 384 KB
subtask2_10.txt AC 8 ms 384 KB
subtask2_11.txt AC 8 ms 384 KB
subtask2_12.txt AC 8 ms 384 KB
subtask2_13.txt AC 3 ms 256 KB
subtask2_14.txt AC 8 ms 384 KB
subtask2_15.txt AC 8 ms 384 KB
subtask2_16.txt AC 8 ms 384 KB
subtask2_17.txt AC 8 ms 384 KB
subtask2_18.txt AC 3 ms 256 KB
subtask2_19.txt AC 8 ms 384 KB
subtask2_20.txt AC 8 ms 384 KB