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
hide comments
Pawe³ Tarasiuk:
2016-05-28 22:58:07
Got AC, wanted to give this task to students, but there seems to be a problem with the constraints.
|
|
ash_hacker:
2016-03-24 12:22:05
Done with naive approach, didn't calculated each exponent individually, just multiply x progressively to get each exponent. |
|
Arpit Gupta:
2016-03-05 13:41:14
Guess what... :D 2007th solver of the problem.... coincidences do happen... :) |
|
abc_c:
2016-02-14 13:41:33
TLE in naive method, AC using Horner !!
|
|
minhthai:
2016-01-07 11:44:48
For Java don't use Scanner, it's too slow |
|
Mateusz Kwasniak:
2015-08-31 15:21:08
God damn,
|
|
Gaurav Jain:
2015-07-28 14:21:16
Simple one. Did it in linear time using horner. |
|
SangKuan:
2015-07-05 12:30:45
very easy,but got 3 wa |
|
swordfish12:
2015-02-28 11:07:44
very simple.....
|
|
UnrealNinja:
2013-12-30 19:42:07
For slower languages like Java and Python, you would need a Linear Time Algorithm with small coefficient and Fast I/O to get Accepted. |
Added by: | Ivan Alfonso Olamendy |
Date: | 2007-08-25 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | My own resource |