Hide

# Problem AMaster Theorem

Many Divide and Conquer (D&C) algorithms have time complexities that can be characterized as the following standard recurrence: $T(n) = a \cdot T(n/b) + c \cdot n^ d \log ^ k n$. Note that $c \cdot n^ d \log ^ k n$ is just the general form of $f(n)$ so that we can capture as many forms of function $f(n)$ as possible. We have just learned about the master theorem. Master theorem has three possible cases:

1. If there exists a constant $\epsilon > 0$ such that $f(n) = O(n^{\log _ b a - \epsilon })$, then $T(n) = \Theta (n^{\log _ b a})$

2. If there exists a constant $k$ such that $f(n) = \Theta (n^{\log _ b a} \log ^ k n)$, then:

1. If $k \geq 0$, then $T(n) = \Theta (n^{\log _ b a} \log ^{k+1} n)$

2. If $k = -1$, then $T(n) = \Theta (n^{\log _ b a} \log \log n)$

3. If $k < -1$, then $T(n) = \Theta (n^{\log _ b a})$

3. If there exists a constant $\epsilon > 0$ such that $f(n) = \Omega (n^{log_ b a + \epsilon })$, and if $f(n)$ additionally satisfies the regularity condition $a \cdot f(n/b) \leq C \cdot f(n)$ for some constant $C < 1$ and all sufficiently large $n$, then $T(n) = \Theta (f(n))$

Now it is time to master the master theorem, by writing a program that can automatically churn out the asymptotic time complexity in the following format: "n^x log^k n" or n^x log log n (without the quotes). Obviously, we want our output format to be as nice as possible for human readers, so here are some additional formatting requirements.

For $x$:

• If $x = 0$, print nothing instead of "n^0".

• If $x = 1$, print "n" instead of "n^1".

• If $x$ is an integer, do not print any trailing decimal points, i.e., print "n^2" instead of "n^2.0".

• Otherwise, round $x$ to the nearest tenth and print that, i.e., print "n^1.5" instead of "n^1.45", print "n^2.8" instead of "n^2.807354", etc.

For $k$:

• If $k = 0$, print nothing instead of "log^0 n".

• If $k = 1$, print "log n" instead of "log^1 n".

Please ensure there are no leading nor trailing space(s) in your output other than a single space between "n^x" and ("log^k n" or "log log n"), if both of them are present.

## Input

Each test case contains five numbers: integer $a$, floating-point $b$, floating-point $c$, floating-point $d$, and integer $k$ as denoted in the problem description ($0 < a$, $c \leq 77$; $1 < b \leq 77$; $0 \leq d \leq 77$; $-77 \leq k \leq 77$). Floating-point numbers $b$, $c$, $d$ have at most 7 digits after decimal point.

## Output

Print the required answer in one line. However, if master theorem is not actually applicable for the given test case, print "not applicable" (without the quotes) instead.

1. ($19$ Points): All test cases in this subtask fall into case 1 of master theorem, e.g., Sample Input 1.

2. ($22$ Points): All test cases in this subtask fall into case 2 of master theorem and $k \geq 0$, e.g., Sample Input 2.

3. ($21$ Points): All test cases in this subtask fall into case 3 of master theorem, e.g., Sample Input 3.

4. ($15$ Points): All test cases in this subtask has $k < 0$, e.g., Sample Input 4.

5. ($23$ Points): No additional constraints. There are $23$ test cases in this subtask and each correct answer worth 1 point.

Sample Input 1 Sample Output 1
4 2.0 2.1 0.0 0

n^2

Sample Input 2 Sample Output 2
2 2.0 2.8 1.0 0

n log n

Sample Input 3 Sample Output 3
4 2.0 1.3 3.0 0

n^3

Sample Input 4 Sample Output 4
2 2.0 2.8 1.0 -1

n log log n

Hide