Japan Alumni Group Summer Camp 2013 Warming Up

Submission #149651

Source codeソースコード

#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

Task問題 B - Cans of Toys
User nameユーザ名 042_tailed
Created time投稿日時
Language言語 C++ (GCC 4.4.7)
Status状態 AC
Score得点 100
Source lengthソースコード長 2506 Byte
File nameファイル名
Exec time実行時間 575 ms
Memory usageメモリ使用量 932 KB

Test case

Set

Set name Score得点 / Max score Cases
all 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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