Submission #149651
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <cstdlib>
#include <numeric>
#include <bitset>
#include <cstring>
#include <iomanip>
using namespace std;
#define REP(i, m, n) for(int i=(m); i<int(n); ++i)
#define rep(i, n) for(int i=0; i<int(n); ++i)
#define each(it, a) for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
//#define FILL(a, c) std::fill((__typeof(c)*)(a), (__typeof(c)*)(a) + sizeof(a) / sizeof(__typeof(c)), (c))
#define FILL(a, c) fill_n(reinterpret_cast<__typeof(c)*>(a), sizeof(a) / sizeof(__typeof(c)), (c))
template<class T> void fill_n(const T *first, size_t n, const T &value) { for(; n>0; --n) *const_cast<T*>(first++) = value; }
#define pb push_back
#define mp make_pair
#define def(a, x) __typeof(x) a = x
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> PI;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
vector<double> companion_mult(const vector<double> &coeff, const vector<double> &u, const vector<double> &v) {
const int k = sz(coeff)-1;
vector<double> c(k*2, 0);
rep(i, k) rep(j, k) c[i+j] += u[i] * v[j];
double z = u[k];
rep(i, k) z += u[i] * v[k];
for(int i=k*2-1; i>=k; i--) rep(j, k+1) (j==k ? z : c[i-k+j]) += c[i] * coeff[j];
c.resize(k+1);
c[k] = z;
return c;
}
double solve_recursion_with_const(const vector<double> &coeff, const vector<double> &init, ll p) {
const int k = sz(init);
assert(p >= 0 && k+1 == sz(coeff) && k >= 1);
vector<double> x(k+1, 0), b(k+1, 0);
x[0] = 1;
if (k == 1) b = coeff; else b[1] = 1;
for(; p > 0; p>>=1, b = companion_mult(coeff, b, b)) if (p&1) x = companion_mult(coeff, x, b);
double res = x[k];
rep(i, k) res += init[i] * x[i];
return res;
}
int main() {
double p, q, r;
cin >> p >> q >> r;
double s = p+q+r;
ll N, K, M;
cin >> N >> K >> M;
vector<double> coeff(N*K+1, 0);
coeff[0] += r/s;
coeff[N*K-N] += p/s;
coeff[N*K-1] += q/s;
coeff[N*K] += 1.0/s;
double res = solve_recursion_with_const(coeff, vector<double>(N*K, 0.0), M*N+N*K-1);
printf("%.20f\n", res);
}
Submission Info
Submission Time |
|
Task |
B - Cans of Toys |
User |
tailed |
Language |
C++ (GCC 4.4.7) |
Score |
100 |
Code Size |
2506 Byte |
Status |
AC |
Exec Time |
575 ms |
Memory |
932 KB |
Judge Result
Set Name |
all |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
all |
1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 4, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 5, 6, 7, 8, 9 |
Case Name |
Status |
Exec Time |
Memory |
1 |
AC |
21 ms |
808 KB |
10 |
AC |
21 ms |
812 KB |
11 |
AC |
21 ms |
928 KB |
12 |
AC |
21 ms |
792 KB |
13 |
AC |
80 ms |
932 KB |
14 |
AC |
39 ms |
808 KB |
15 |
AC |
20 ms |
800 KB |
16 |
AC |
26 ms |
736 KB |
17 |
AC |
74 ms |
804 KB |
18 |
AC |
384 ms |
924 KB |
19 |
AC |
39 ms |
800 KB |
2 |
AC |
21 ms |
800 KB |
20 |
AC |
26 ms |
804 KB |
21 |
AC |
27 ms |
804 KB |
22 |
AC |
49 ms |
772 KB |
23 |
AC |
21 ms |
680 KB |
24 |
AC |
23 ms |
740 KB |
25 |
AC |
20 ms |
800 KB |
26 |
AC |
20 ms |
924 KB |
27 |
AC |
201 ms |
800 KB |
28 |
AC |
21 ms |
800 KB |
29 |
AC |
23 ms |
808 KB |
3 |
AC |
21 ms |
804 KB |
30 |
AC |
21 ms |
708 KB |
31 |
AC |
204 ms |
800 KB |
32 |
AC |
22 ms |
804 KB |
33 |
AC |
22 ms |
796 KB |
34 |
AC |
21 ms |
800 KB |
35 |
AC |
575 ms |
800 KB |
36 |
AC |
21 ms |
804 KB |
37 |
AC |
23 ms |
924 KB |
38 |
AC |
23 ms |
812 KB |
39 |
AC |
575 ms |
804 KB |
4 |
AC |
21 ms |
808 KB |
40 |
AC |
225 ms |
740 KB |
41 |
AC |
328 ms |
804 KB |
42 |
AC |
175 ms |
736 KB |
43 |
AC |
271 ms |
736 KB |
44 |
AC |
201 ms |
804 KB |
45 |
AC |
68 ms |
808 KB |
46 |
AC |
290 ms |
924 KB |
47 |
AC |
204 ms |
740 KB |
48 |
AC |
224 ms |
804 KB |
49 |
AC |
94 ms |
800 KB |
5 |
AC |
202 ms |
804 KB |
6 |
AC |
21 ms |
844 KB |
7 |
AC |
22 ms |
928 KB |
8 |
AC |
22 ms |
736 KB |
9 |
AC |
21 ms |
804 KB |