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
2015-10-16 16:43:27+0900
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
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