SPOJ CMPLS

From Algorithmist
Jump to navigation Jump to search

8 (CMPLS) - Complete the Sequence![edit]

Summary[edit]

The problem states that given some initial terms of a sequence whose terms are of the form of a polynomial where is the term number, you have to find some numbers completing the sequence to a given term number.

Explanation[edit]

Note that the polynomial in n is not given, neither its order is given.

Let us assume that the order of polynomial is . The problem is quite simple when you notice that where is a polynomial of the order . Hence, if we keep on subtracting consecutive terms of the sequence, we would get another sequence with order . Keep on repeating the process for the new sequence till you get all terms as constant (equal). This actually means that the order has now become 0.

Now append the same constant the number of times as asked in the question and carry out the reverse procedure to get back to the original sequence with additional terms.

Note that it is not necessary to explicitly compute the polynomial. Doing so is more complicated to code and could lead to floating point precision errors.

Input[edit]

4
6 3
1 2 3 4 5 6
8 2
1 2 4 7 11 16 22 29
10 2
1 1 1 1 1 1 1 1 1 2
1 10
3

Output[edit]

7 8 9
37 46
11 56
3 3 3 3 3 3 3 3 3 3