|
Bisection
Method Input: Standard Input Output: Standard Output |
|
Bisection method is a very basic
and robust numerical method for finding roots of an equation. Finding the roots of a nonlinear equation
which f(x)=0 is equivalent to finding the values of x for
which f(x) is zero or approximately zero. In bisection method to find
the roots of an equation we first
need two initial guesses xl and xu which bracket a
root (Or more than one root), that means 
. This ensures that the function must become zero somewhere
in between and so it is guaranteed that there is at least one root between xl and xu. The
bisection algorithm works the following way:
1. Choose xl and xu such that 
and xl < xu
2. Estimate the approximate root 
3. 
4. If root is not
found go back to 2.
In this problem your job is not to find the roots of a function f(x) using bisection method. In this problem you will be given an equation of the form (x-r1)(x-r2)(x-r3)... (x-rn)=0, so it is obvious that the roots of this equation are r1, r2, r3,..., rn. For this problem all the roots are strictly positive integers less than 10000 and the range of xl and xu is 0 ≤ xl < xu ≤ 10000. Now your job is to find that for a given root, how many possible pairings of (xl, xu) are there for which that root is found in at most 7 steps?
Input
First line of the input file contains a positive integer N (1 ≤ N ≤ 30) which denotes how many sets of inputs are there. Each set of input consists of two lines. The description of the two lines are given below:
The first line of each set consists of an equation of the form (x-r1)(x-r2)(x-r3)... (x-rn)=0. Here r1, r2, r3,..., rn are all integers, 0 < r1, r2, r3,..., rn < 10000 and 0 < n < 11. The second line contains an integer r, whose value is equal to any one of the roots.
Output
For each set of input produce one line of output. This line contains an integer which denotes of all the pairings of possible values for which root r will be found using bisection method in seven steps or less. Note that as the possible values for xl and xu is in the range from 0 to 10000. So possible pairings xi and xu are (0, 1), (0, 2), (0, 3), ...,(0, 10000), (1, 2), (1, 3), (1, 4), ..., (1, 10000), ..., (9999,10000). So total number of pairings are (10001)(10001-1)/2. Of which only small number of pairings will ensure that root r is found within 7 iterations.
Sample
Input Output for Sample Input
|
2 (x-8469)(x-6335)=0 8469 (x-2384)(x-7423)(x-8718)=0 8718 |
8930 6530 |
Problemsetter: Shahriar Manzoor, Special Thanks: Md.
Mahbubul Hasan