Submission #103423


Source Code Expand

import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;

class Reader {
    BufferedReader br;
    StringTokenizer st;
    Reader(InputStream is) {
	br = new BufferedReader(new InputStreamReader(is));
	st = null;
    }
    String next() {
	while (st == null || !st.hasMoreTokens()) {
	    try {
		st = new StringTokenizer(br.readLine());
	    } catch (Exception e) {
		e.printStackTrace();
	    }
	}
	return st.nextToken();
    }
    int nextInt() {
	return Integer.parseInt(next());
    }
    Long nextLong() {
	return Long.parseLong(next());
    }
    Double nextDouble() {
	return Double.parseDouble(next());
    }
}

class Poly {
    BigDecimal[] mul(BigDecimal[] a, BigDecimal[] b, BigDecimal[] c) {
	int n = a.length;
	BigDecimal[] r = new BigDecimal[n*2];
	for (int i=0; i<n*2; i++) r[i] = new BigDecimal(0.0);

	for (int i=0; i<n; i++) {
	    for (int j=0; j<n; j++) {
		r[i+j] = r[i+j].add(a[i].multiply(b[j]));
	    }
	}
	for (int i=n*2; i-->n; ) {
	    for (int j=1; j<=n; j++) {
		r[i-j] = r[i-j].add(r[i].multiply(c[n-j]));
	    }
	}
	BigDecimal[] s = new BigDecimal[n];
	System.arraycopy(r, 0, s, 0, n);
	return s;
    }
    BigDecimal[] pow(BigDecimal[] a, Long y, BigDecimal[] c) {
	int n = a.length;
	BigDecimal[] r = new BigDecimal[n];
	for (int i=0; i<n; i++) r[i] = new BigDecimal(0.0);

	r[0] = new BigDecimal(1.0);
	for (; y > 0; y >>= 1) {
	    if ((y&1) == 1) r = mul(r, a, c);
	    a = mul(a, a, c);
	}
	return r;
    }
}

class Main {
    public static void main(String[] args) {
	new Main().solve();
    }
    void solve() {
	Reader in = new Reader(System.in);
	PrintStream out = System.out;

	double p = in.nextDouble();
	double q = in.nextDouble();
	double r = in.nextDouble();

	int N = in.nextInt();
	int K = in.nextInt();
	long M = in.nextLong();

	BigDecimal[] v = new BigDecimal[N*K+1];
	for (int i=0; i<N*K+1; i++) v[i] = new BigDecimal(0.0);
	double base = (p+q+r);

	v[0] = v[0].add(new BigDecimal(-r / base));
	v[1] = v[1].add(new BigDecimal(r / base));
	v[N*(K-1)] = v[N*(K-1)].add(new BigDecimal(-p / base));
	v[N*(K-1) + 1] = v[N*(K-1)+1].add(new BigDecimal(p / base));
	v[N*K-1] = v[N*K-1].add(new BigDecimal(-q / base));
	v[N*K] = v[N*K].add(new BigDecimal((p + 2*q + r) / base));

	BigDecimal[] alpha = new BigDecimal[N*K+1];
	for (int i=0; i<N*K+1; i++) alpha[i] = new BigDecimal(0.0);

	alpha[0] = new BigDecimal(0.0);
	for (int i=1; i<=N*K; i++) {
	    if (i>=N) alpha[i] = alpha[i].add(alpha[i-N].multiply(new BigDecimal(p)));
	    if (i >= 1) alpha[i] = alpha[i].add(alpha[i-1].multiply(new BigDecimal(q)));
	    if (i >= N*K) alpha[i] = alpha[i].add(alpha[i-N*K].multiply(new BigDecimal(r)));
	    alpha[i] = alpha[i].add(new BigDecimal(1.0));
	    alpha[i] = alpha[i].divide(new BigDecimal(base), 50, RoundingMode.HALF_EVEN);
	}

	BigDecimal[] beta = new BigDecimal[N*K+1];
	for (int i=0; i<N*K+1; i++) beta[i] = new BigDecimal(0.0);

	beta[1] = new BigDecimal(1.0);
	beta = new Poly().pow(beta, M*N, v);

	BigDecimal ans = new BigDecimal(0.0);
	for (int i=0; i<N*K+1; i++) ans = ans.add(beta[i].multiply(alpha[i]));

	//out.format("%.6f\n", ans);
	out.println(ans.toString());
    }
}

Submission Info

Submission Time
Task B - Cans of Toys
User natsugiri
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 3278 Byte
Status TLE
Exec Time 1688 ms
Memory 41108 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 9
TLE × 40
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 619 ms 21396 KB
10 TLE 1552 ms 34860 KB
11 TLE 1544 ms 34704 KB
12 TLE 1538 ms 33660 KB
13 TLE 1538 ms 34204 KB
14 TLE 1538 ms 34480 KB
15 TLE 1549 ms 34368 KB
16 TLE 1536 ms 34240 KB
17 TLE 1538 ms 33952 KB
18 TLE 1554 ms 36156 KB
19 TLE 1538 ms 33784 KB
2 AC 423 ms 21304 KB
20 TLE 1540 ms 33944 KB
21 TLE 1538 ms 36580 KB
22 TLE 1537 ms 34172 KB
23 TLE 1538 ms 41108 KB
24 AC 419 ms 21428 KB
25 TLE 1540 ms 39920 KB
26 AC 489 ms 23776 KB
27 TLE 1539 ms 36516 KB
28 AC 416 ms 21296 KB
29 TLE 1539 ms 40312 KB
3 AC 448 ms 23476 KB
30 AC 514 ms 23760 KB
31 TLE 1538 ms 38016 KB
32 TLE 1688 ms 27520 KB
33 TLE 1540 ms 39720 KB
34 TLE 1538 ms 34612 KB
35 TLE 1542 ms 37376 KB
36 TLE 1675 ms 27756 KB
37 TLE 1539 ms 39264 KB
38 TLE 1540 ms 39864 KB
39 TLE 1537 ms 36848 KB
4 AC 423 ms 21304 KB
40 TLE 1539 ms 34808 KB
41 TLE 1539 ms 36860 KB
42 TLE 1537 ms 34412 KB
43 TLE 1537 ms 34908 KB
44 TLE 1540 ms 34388 KB
45 TLE 1536 ms 34172 KB
46 TLE 1557 ms 36576 KB
47 TLE 1538 ms 34180 KB
48 TLE 1539 ms 34392 KB
49 TLE 1538 ms 33732 KB
5 TLE 1539 ms 39092 KB
6 TLE 1537 ms 37036 KB
7 TLE 1552 ms 34928 KB
8 AC 440 ms 22704 KB
9 TLE 1546 ms 35252 KB