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 |
|
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 |