Submission #528061


Source Code Expand

/*{{{*/
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
typedef int8_t sbyte;
typedef uint8_t byte;
typedef uint16_t ushort;
typedef uint32_t uint;
typedef int64_t i64;
typedef uint64_t u64;
template<class T> static inline T ABS(T x) {return x < 0 ? -x : x;}
template<class T> static inline void MAZ(T &a, const T &b) {if(a < b) a = b;}
template<class T> static inline void MIZ(T &a, const T &b) {if(b < a) a = b;}
/*}}}*/

static const int POW[] = {101 * 101, 101, 1};

static int S[81][4];
static int N[3];
static int P[3], Q[3];
static int R[3];
static double DP[101 * 101 * 101];

static inline int myhash(const int *r) {
	return r[0] * 101 * 101 + r[1] * 101 + r[2];
}

static void solve() {
	auto hR = myhash(R);
	if(hR == 0) return;
	auto ret = 1e100;
	for(auto s = 0; s < 81; s++) {
		if(R[S[s][0]] == 0) continue;
		if(R[1] >= 4 && R[2] >= 4 && S[s][3] != 0) {
			if(P[S[s][3]] > P[3 - S[s][3]] || P[S[s][3]] == P[3 - S[s][3]] && S[s][3] == 2) continue;
		}
		auto ta = 0., tb = 1.;
		auto p = 1, q = 1;
		int r[3] = {R[0], R[1], R[2]};
		auto hr = hR;
		for(auto i = 0; i < 4; i++) {
			auto lvl = S[s][i];
			if(r[lvl] == 0) {
				tb += DP[hr] * p / q;
				break;
			}
			if(Q[lvl] != 0) {
				if(hr != hR) {
					tb += DP[hr] * (p * Q[lvl]) / (q * 100);
				} else {
					ta += p * Q[lvl] / (double)(q * 100);
				}
			}
			r[lvl]--;
			hr -= POW[lvl]; //hr = myhash(r);
			p *= P[lvl];
			q *= 100;
			if(i == 2 && lvl == 0 || i == 3) {
				tb += DP[hr] * p / q;
				break;
			}
		}
		MIZ(ret, tb / (1 - ta));
	}
	DP[hR] = ret;
}

static void solve_dfs(int dep) {
	if(dep == 3) {
		solve();
	} else {
		for(auto n = 0; n <= N[dep]; n++) {
			R[dep] = n;
			solve_dfs(dep + 1);
		}
	}
}

static void build() {
	for(auto s = 0; s < 81; s++) {
		auto t = s;
		for(auto i = 4; --i >= 0; ) {
			S[s][i] = t % 3;
			t /= 3;
		}
	}
}

int main() {
	build();
	for(auto i = 0; i < 3; i++) scanf("%d", N + i);
	for(auto i = 0; i < 3; i++) {
		scanf("%d", P + i);
		Q[i] = 100 - P[i];
	}
	solve_dfs(0);
	printf("%.15f\n", DP[myhash(N)]);
	return 0;
}

Submission Info

Submission Time
Task E - Game
User arosusti
Language C++11 (GCC 4.8.1)
Score 0
Code Size 2575 Byte
Status TLE
Exec Time 2037 ms
Memory 9008 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:112:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(auto i = 0; i < 3; i++) scanf("%d", N + i);
                                                ^
./Main.cpp:114:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", P + i);
                     ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 5
AC × 19
TLE × 3
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask0_sample_05.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask0_sample_05.txt, subtask1_manual_01.txt, subtask1_manual_02.txt, subtask1_manual_03.txt, subtask1_manual_04.txt, subtask1_manual_05.txt, subtask1_manual_06.txt, subtask1_manual_07.txt, subtask1_random_01.txt, subtask1_random_02.txt, subtask1_random_03.txt, subtask1_random_04.txt, subtask1_random_05.txt, subtask1_random_06.txt, subtask1_random_07.txt, subtask1_random_08.txt, subtask1_random_09.txt, subtask1_random_10.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 27 ms 1036 KB
subtask0_sample_02.txt AC 1644 ms 9008 KB
subtask0_sample_03.txt AC 27 ms 1044 KB
subtask0_sample_04.txt AC 28 ms 972 KB
subtask0_sample_05.txt AC 41 ms 1200 KB
subtask1_manual_01.txt AC 28 ms 1044 KB
subtask1_manual_02.txt AC 27 ms 1040 KB
subtask1_manual_03.txt AC 29 ms 1048 KB
subtask1_manual_04.txt TLE 2037 ms 4140 KB
subtask1_manual_05.txt TLE 2037 ms 4204 KB
subtask1_manual_06.txt AC 1591 ms 8864 KB
subtask1_manual_07.txt TLE 2037 ms 5540 KB
subtask1_random_01.txt AC 1001 ms 6440 KB
subtask1_random_02.txt AC 382 ms 2224 KB
subtask1_random_03.txt AC 308 ms 3500 KB
subtask1_random_04.txt AC 111 ms 1192 KB
subtask1_random_05.txt AC 567 ms 2344 KB
subtask1_random_06.txt AC 977 ms 6056 KB
subtask1_random_07.txt AC 389 ms 2604 KB
subtask1_random_08.txt AC 668 ms 2468 KB
subtask1_random_09.txt AC 448 ms 2600 KB
subtask1_random_10.txt AC 384 ms 2124 KB