Problem C
Simple Sequence
Yu is learning about recursive sequences in his math class. Recursive sequences are described by recurrence relations. To complete his homework that is too hard for him, he needs a recurrence sequence calculator (assume this doesn’t count as cheating in this case). Yu is not a programmer, but you are, so Yu asked you to make Yu one.
A recurrence relation is a mathematical equation that defines a sequence of numbers by relating each term to the previous terms. For example, the Fibonacci sequence: $1, 1, 2, 3, 5, 8, 13, 21, \ldots $, in which each number is the sum of last two previous numbers, can be described with this relation:
\[ F_n = F_{n-1} + F_{n-2} \]Like all recursions, this one too must be terminated. Recursive sequences need initial conditions - in the case of the Fibonacci sequence, these are $1$ for both the $1^{\text{st}}$ and $2^{\text{nd}}$ terms $F_1$ and $F_2$.
Your task is to output the $m^{\text{th}}$ term of a sequence for which the recurrence equation, some initial conditions, and $m$ are given.
Input
The input has three lines, the first line contains an integer $m$ ($1 \leq m \leq 50$), where the $m^{\text{th}}$ term is the one you need to find.
The second line is the expression for the $n^{\text{th}}$ term of the recurrence relation. This expression will contain real number constants $c$ in the range $-10^{4} \leq c \leq 10^{4}$; operators including addition, subtraction, multiplication, and division; parentheses; and terms of the form F(n-k) (with no spaces) where $k$ is an integer constant ($1 \leq k \leq 6$), representing the $n-k^{\text{th}}$ term $F_{n-k}$. All the individual tokens of an expression (constants, operators, parentheses, and F(n-k) terms) will be separated with a space, and there will be at most $20$ tokens in the expression.
The third line contains a sequence of $i$ initial conditions ($0 < i \leq 6$), which are space-separated real numbers $F_k$ ($-10^{4} \leq F_k \leq 10^{4}$) starting from left to right with $F_1$, $F_2$, and so on up to the number of constants on the line. You are guaranteed that there are $k$ initial conditions for the maximum value $k$ that may occur in a term of the form $F(n-k)$ in the expression.
You are guaranteed that the evaluation of these expressions for input $m$ will not involve undefined operations such as division by zero, and that the result can be computed using IEEE-754 double precision floating point arithmetic without over- or underflow.
Output
Output the $m^{\text{th}}$ term of the recurrence relation. Your answer will be considered correct if it is within an relative or absolute error of $10^{-4}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 F(n-1) + F(n-2) 1 1 |
55 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 F(n-1) * 2 1 |
16 |
| Sample Input 3 | Sample Output 3 |
|---|---|
20 ( F(n-1) - 3 * F(n-3) ) / F(n-2) 1 -3.5 2.5 |
71.44292214372034 |
