Problem B
Generalized Recursive Functions
You have been employed by the math department to find the solutions to different recursive, integer-valued functions. Every function is of the form:
\[ f(x,y) = \left\{ \begin{array}{ll} f(x-a_1,y-b_1)+f(x-a_2,y-b_2)+\ldots +f(x-a_ n,y-b_ n)+c, & \text {if $x, y > 0$} \\ d, & \text {otherwise} \end{array} \right. \]where all parameters $a_ i, b_ i, c, d$ are non-negative integers, and for each $i$, $a_ i+b_ i > 0$. Write a program that, given the parameters, determines the value of the function for various inputs $x$ and $y$.
Input
Input starts with an integer $1 \le n \le 100$, indicating the number of cases that follow. Each test case has two lines. The first line is the description $0$ to $20$ pairs of $a_ i$ and $b_ i$ values, followed by $c$ and $d$. The second line is a sequence of $1$ to $20$ pairs of inputs $x$ and $y$. All inputs are integers in the range $[0,99]$, separated within each line by spaces.
Output
For each $x, y$ input to the function, output the value $f(x,y)$. Print each output on its own line and separate functions with a blank line.
Sample Input 1 | Sample Output 1 |
---|---|
2 2 0 1 0 0 1 0 0 1 0 1 1 2 1 3 1 4 1 5 1 6 1 1 0 0 1 1 1 1 0 0 0 20 20 |
1 1 2 3 5 8 13 21 0 130271906898720 |