Algorithm
problem link- https://www.spoj.com/problems/POLEVAL/
POLEVAL - Evaluate the polynomial
Your task consists of evaluate a polynomial of degree n (0 <= n <= 999) represented by its n+1 coefficients of the form:
in each one of the k (1 <= k <= 100) points x1, x2, …, xk. The coefficients of the polynomial and the values where they will be evaluated are integers in the interval [-100, 100] that guarantees that the polynomial's evaluation is at the most 263 – 1.
Input
There will be multiple test cases, each one with 4 lines that are described below
n: degree of polynomial.
cn cn-1 … c2 c1 c0: coefficients of the polynomial separated by a single space.
k: number of points to evaluate the polynomial.
x1 x2 … xk-1 xk: points to evaluate the polynomial separated by a single space.
The final test case is a single line where n = -1 and this case should not be processed.
Output
For each test case you should print k + 1 lines of output, the very first line containing the case number and the following k lines with the result of the polynomial's evaluation in each one of the k given points. See the sample.
Example
Input: 2
1 -2 -1
5
0 1 -1 2 -2
3
2 1 -2 -1
4
0 -1 2 -2
-1
Output: Case 1:
-1
-2
2
-1
7
Case 2:
-1
0
15
-9
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int main()
{
int n,k,a[1000],p[100],z=1;
long long ans=0,x;
while(true)
{
scanf("%d",&n);
if(n==-1)
break;
for(int i=0;i <=n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&k);
for(int i=0;i <k;i++)
{
scanf("%d",&p[i]);
}
printf("Case %d:\n",z++);
for(int i=0;i <k;i++)
{
ans=0;
x=1;
for(int j=n;j>=0;j--)
{
ans=ans+a[j]*x;
x=x*p[i];
}
printf("%I64d\n", ans);
}
}
}Input
1 -2 -1
5
0 1 -1 2 -2
3
2 1 -2 -1
4
0 -1 2 -2
-1
Output
-1
-2
2
-1
7
Case 2:
-1
0
15
-9
Demonstration
SPOJ Solution-POLEVAL Evaluate the polynomial-Solution in C, C++, Java, Python