結果

問題 No.301 サイコロで確率問題 (1)
ユーザー h_nosonh_noson
提出日時 2016-06-20 00:35:58
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,131 bytes
コンパイル時間 619 ms
コンパイル使用メモリ 74,476 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-11 05:24:41
合計ジャッジ時間 3,989 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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 {
    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<double> operator*(vector<double> b) {
        vector<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;
        M a, b;
        a.init();
        b.init2();
        while (n) {
            if (n % 2)
                a = a * b;
            b = b * b;
            n /= 2;
        }
        vector<double> c(7);
        double l, r;
        l = 0; r = 1e18;
        for (int loop = 0; loop < 1000; loop++) {
            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;
    }
    return 0;
}
0