結果

問題 No.301 サイコロで確率問題 (1)
ユーザー h_nosonh_noson
提出日時 2016-06-20 01:12:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 417 ms / 1,000 ms
コード長 2,364 bytes
コンパイル時間 549 ms
コンパイル使用メモリ 75,092 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-19 13:03:39
合計ジャッジ時間 1,851 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 417 ms
6,812 KB
testcase_01 AC 24 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iomanip>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e8
#define MOD (int)(1e9+7)

typedef long long ll;

struct M {
    long double mat[7][7] {};

    void init() {
        for (int i = 0; i < 7; i++)
            mat[i][i] = 1;
    }

    void init2() {
        mat[0][0] = 1;
        for (int j = 0; j < 7; j++)
            mat[1][j] = 1./6;
        mat[1][0] = 1;
        for (int i = 0; i < 5; i++)
            mat[i+2][i+1] = 1;
    }

    M operator*(M& b) {
        M c;
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                for (int k = 0; k < 7; k++) {
                    c.mat[i][j] += mat[i][k] * b.mat[k][j];
                }
            }
        }
        return c;
    }

    vector<long double> operator*(vector<long double> b) {
        vector<long double> c(7);
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                c[i] += mat[i][j] * b[j];
            }
        }
        return c;
    }

    void print() {
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++)
                cout << mat[i][j] << " ";
            cout << endl;
        }
    }
};

int main(void) {
    int t;
    ll n;
    cin >> t;
    while (t--) {
        cin >> n;
        if (n < 100000) {
            M a, b;
            a.init();
            b.init2();
            while (n) {
                if (n % 2)
                    a = a * b;
                b = b * b;
                n /= 2;
            }
            vector<long double> c(7);
            long double l, r;
            l = 0; r = 1e10;
            for (int loop = 0; loop < 200; loop++) {
                long double m = (l+r)/2;
                c[0] = 1; c[1] = 0;
                for (int i = 2; i < 7; i++)
                    c[i] = m;
                c = a * c;
                if (c[1] > m)
                    l = m;
                else
                    r = m;
            }
            cout << fixed << setprecision(13) << (l+r)/2 << endl;
        }
        else
            cout << (n+1) << ".666666666666" << endl;
    }
    return 0;
}
0