結果

問題 No.75 回数の期待値の問題
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-04-28 01:18:34
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 4,743 ms / 5,000 ms
コード長 2,816 bytes
コンパイル時間 1,801 ms
コンパイル使用メモリ 147,680 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-18 14:01:09
合計ジャッジ時間 102,342 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4,722 ms
4,376 KB
testcase_01 AC 4,723 ms
4,376 KB
testcase_02 AC 4,724 ms
4,380 KB
testcase_03 AC 4,722 ms
4,376 KB
testcase_04 AC 4,724 ms
4,380 KB
testcase_05 AC 4,723 ms
4,380 KB
testcase_06 AC 4,721 ms
4,376 KB
testcase_07 AC 4,723 ms
4,380 KB
testcase_08 AC 4,723 ms
4,380 KB
testcase_09 AC 4,722 ms
4,376 KB
testcase_10 AC 4,723 ms
4,380 KB
testcase_11 AC 4,725 ms
4,380 KB
testcase_12 AC 4,720 ms
4,380 KB
testcase_13 AC 4,722 ms
4,376 KB
testcase_14 AC 4,722 ms
4,380 KB
testcase_15 AC 4,723 ms
4,380 KB
testcase_16 AC 4,721 ms
4,376 KB
testcase_17 AC 4,725 ms
4,380 KB
testcase_18 AC 4,743 ms
4,376 KB
testcase_19 AC 4,723 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int N = 624;
const int M = 397;
const unsigned int MATRIX_A = 0x9908b0dfU;
const unsigned int UPPER_MASK = 0x80000000U;
const unsigned int LOWER_MASK = 0x7fffffffU;

vector<unsigned int> mt;
int mti = N + 1;

void init_genrand(unsigned int s) {
    mt.push_back(s & 0xffffffffU);
    for(mti=1; mti<N; mti++) {
        mt.push_back(1812433253U * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
        mt[mti] &= 0xffffffffU;
    }
}

void init_by_array(vector<unsigned int> init_key) {
    int key_length = init_key.size();
    init_genrand(19880731U);
    int i = 1, j = 0;
    int k = N > key_length ? N : key_length;
    for( ; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525U)) + init_key[j] + j;
        mt[i] &= 0xffffffffU;
        i++; j++;
        if(i >= N) { mt[0] = mt[N-1]; i = 1; }
        if(j >= key_length) { j = 0; }
    }
    for(k=N-1; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941U)) - i;
        mt[i] &= 0xffffffffU;
        i++;
        if(i >= N) { mt[0] = mt[N-1]; i = 1; }
    }
    mt[0] = 0x80000000U;
}

unsigned int genrand_int32(void) {
    unsigned int y;
    static unsigned int mag01[2] = {0x0U, MATRIX_A};
    if(mti >= N) {
        if(mti == N + 1) { init_genrand(5489U); }
        int kk;
        for(kk=0; kk<N-M; kk++) {
            y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
        }
        for(; kk<N-1; kk++) {
            y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
        }
        y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];
        mti = 0;
    }
    y = mt[mti++];
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680U;
    y ^= (y << 15) & 0xefc60000U;
    y ^= (y >> 18);
    return y;
}

int genrand_int31(void) {
    return (int)(genrand_int32() >> 1);
}

int main(void) {
    clock_t start = clock();
    time_t now = time(0);
    vector<unsigned int> init;
    init.push_back(0x123);
    init.push_back(0x234);
    init.push_back(0x345);
    init.push_back(0x456);
    init.push_back(now);
    init_by_array(init);

    int k; scanf("%d", &k);
    int times;
    int res = 0;
    for(times=1; ; times++) {
        int cnt;
        int summa = 0;
        for(cnt=1; ; cnt++) {
            int dice = genrand_int31() % 6 + 1;
            summa += dice;
            if(summa > k) { summa = 0; continue; }
            if(summa == k) { break; }
        }
        res += cnt;
        clock_t now = clock();
        if((double)(now - start) / CLOCKS_PER_SEC >= 4.7) { break; }
    }
    printf("%f\n", (float)res/times);
    return 0;
}
0