All submissions for this problem are available.
Do you remember those questions of Sequence and Series chapter of Class 11th in which we were required to find the next number of a particular sequence? If not then let us revise a few concepts first.
The sequences can be generally described by polynomials. For e.g. the sequence 1, 2, 3, 4, 5 can be easily understood as a trivial polynomial. The next number is 6. But even more complex sequences, like 1, 2, 4, 7, 11, can be described by a polynomial, 1/2.n2-1/2.n+1 . Note that even if the members of the sequence are integers, polynomial coefficients may be any real numbers.
Polynomial is an expression in the following form:
P(n) = ak.nk+ak-1.nk-1+...+a1.n+a0
If ak != 0, the number k is called a degree of the polynomial. Note that a constant function of the form P(n) = C is of degree 0, and the zero function P(n) = 0 is of degree -1.
There are multiple test cases in the input. The input begins with a single integer which gives the number of test cases. Each test case consists of two lines. First line of each test case contains two integers L and Q separated by a space, 1 ≤ L < 100, 1 ≤ Q < 100, (L+Q) ≤ 100. Here L is the length of the given sequence and Q is the amount of numbers you are required to find to complete the sequence.
The second line of each test case contains L integer numbers Z1, Z2, ..., ZL separated by a space. These numbers form the given sequence and it can be described by a polynomial P(n) such that for every x, Zx = P(x). Among these polynomials, we can find the polynomial Pmin with the lowest possible degree which is the required polynomial to be used for completing the sequence.
For every test case, print Q integer numbers, which are the values completing the sequence according to the polynomial Pmin, separated by a space, i.e. you need to print Pmin(L+1), Pmin(L+2), ... , Pmin(L+Q).
It is guaranteed that the results Pmin(L+x) will be non-negative integers.
Input: 4 4 4 1 2 3 4 3 4 1 2 4 13 2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 9 7 Output: 5 6 7 8 7 11 16 22 14 92 7 7 7 7 7 7 7 7 7
|Time Limit:||0.259206 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.