Submission #306554

---

Source Code Expand

#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <iterator>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
typedef unsigned long long ull;

double p[3];
double tbl[101][101][101][4];

double dfs(int p1, int p2, int p3,int game) {
	if (tbl[p1][p2][p3][game] >= 0) {
		return tbl[p1][p2][p3][game];
	}
	double ret = 1e300;
	bool first_stage = (game == 0); // 初回
	if (p1 > 0) {
		int ngame = game + 1;
		if (ngame >= 3) ngame = 0; //extraはないので
		double suc = dfs(p1 - 1, p2, p3, ngame);
		double ans;
		if (first_stage) {
			if (p[0] == 1.0) ans = 1 + suc;
			else ans = (1 + suc * p[0]) / p[0];
		} else {
			double fil = dfs(p1, p2, p3, 0);
			ans = suc * p[0] + fil * (1 - p[0]);
		}
		ret = min(ret, ans);
	}
	if (p2 > 0) {
		int ngame = game + 1;
		if (ngame >= 4) ngame = 0; //extraあり！
		double suc = dfs(p1, p2 - 1, p3, ngame);
		double ans;
		if (first_stage) {
			if (p[1] == 1.0) ans = 1 + suc;
			else ans = (1 + suc * p[1]) / p[1];
		} else {
			double fil = dfs(p1, p2, p3, 0);
			ans = suc * p[1] + fil * (1 - p[1]);
		}
		ret = min(ret, ans);
	}
	if (p3 > 0) {
		int ngame = game + 1;
		if (ngame >= 4) ngame = 0; //extraあり！
		double suc = dfs(p1, p2, p3 - 1, ngame);
		double ans;
		if (first_stage) {
			if (p[2] == 1.0) ans = 1 + suc;
			else ans = (1 + suc * p[2]) / p[2];
		} else {
			double fil = dfs(p1, p2, p3, 0);
			ans = suc * p[2] + fil * (1 - p[2]);
		}
		ret = min(ret, ans);
	}

	return tbl[p1][p2][p3][game] = ret;
}

int main() {
	int n[3];
	FOR(i, 3) cin >> n[i];
	FOR(i, 3) cin >> p[i];
	FOR(i,3) p[i] /= 100;
	FOR(p0, 101) {
		FOR(p1, 101) {
			FOR(p2, 101) {
				FOR(i, 4) {
					tbl[p0][p1][p2][i] = -1;
				}
			}
		}
	}

	FOR(i,4) tbl[0][0][0][i] = 0;

	double ans = dfs(n[0], n[1], n[2], 0);
	printf("%.15lf\n", ans);
}

Submission Info

Judge Result