POLEVAL - Evaluate the polynomial

no tags 

Your task consists of evaluate a polynomial of degree n (0 <= n <= 999) represented by its n+1 coefficients of the form:

pn(x) = cnxn + cn-1xn-1 + … + c2x2 + c1x + c0

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.

How do coefficients and values from [-100, 100] guarantee the result to be at most (2**63)-1? For larger (say, >100) polynomial degrees it is kinda guaranteed to overflow for any x other than -1, 0 or 1. Do I miss something here?

=(Francky)=> You can expand polynomials like P(X) = (X-7)(X-12)(X+13)...(X-4) you'll keep not so big P(x) for small x, say |x|<100. It's a possibility... I agree that the description is very poor.

Last edit: 2016-05-29 12:39:02
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 !!
long long Live 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,
I recommend to check if you've got your colon in cases line, before tryharding to correct your algorithm.

Last edit: 2015-08-31 15:21:26
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.....
please put this problem under 'tutorial'

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