結果

問題 No.162 8020運動
コンテスト
ユーザー mamekin
提出日時 2015-03-07 12:51:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,230 bytes
コンパイル時間 1,659 ms
コンパイル使用メモリ 101,688 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-24 15:13:43
合計ジャッジ時間 2,333 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

vector<double> prob(3);
vector<vector<vector<double> > > memo;

double solve(int y, int a, int n)
{
    if(y == 0)
        return n;
    if(memo[y][a][n] > -0.5)
        return memo[y][a][n];

    double ret = 0.0;
    double p = 1.0;
    for(int i=0; i<n; ++i){
        int j = 2;
        if(i == 0 && a == 0)
            -- j;
        if(i == n-1)
            -- j;

        ret += (solve(y - 1, 0, i) + solve(y, 1, n - i - 1)) * (p * prob[j]);
        p *= 1.0 - prob[j];
    }
    ret += solve(y - 1, 0, n) * p;

    return memo[y][a][n] = ret;
}

int main()
{
    int y;
    cin >> y;
    y = 80 - y;
    for(int i=0; i<3; ++i){
        cin >> prob[i];
        prob[i] /= 100.0;
    }

    int n = 14;
    memo.assign(y+1, vector<vector<double> >(2, vector<double>(n+1, -1.0)));
    printf("%.10f\n", solve(y, 0, n) * 2.0);

    return 0;
}
0