Algorithm


Problem link- https://www.spoj.com/problems/CMPLS/

CMPLS - Complete the Sequence!

no tags 

 

You probably know those quizzes in Sunday magazines: given the sequence 1, 2, 3, 4, 5, what is the next number? Sometimes it is very easy to answer, sometimes it could be pretty hard. Because these "sequence problems" are very popular, ACM wants to implement them into the "Free Time" section of their new WAP portal.

ACM programmers have noticed that some of the quizzes can be solved by describing the sequence by polynomials. For example, 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. In this case, 1/2.n2-1/2.n+1 can be used. 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) = aD.nD+aD-1.nD-1+...+a1.n+a0

If aD <> 0, the number D is called a degree of the polynomial. Note that constant function P(n) = C can be considered as polynomial of degree 0, and the zero function P(n) = 0 is usually defined to have degree -1.

 

Input

There is a single positive integer T on the first line of input (equal to about 5000). It stands for the number of test cases to follow. Each test case consists of two lines. First line of each test case contains two integer numbers S and C separated by a single space, 1 <= S < 100, 1 <= C < 100, (S+C) <= 100. The first number, S, stands for the length of the given sequence, the second number, C is the amount of numbers you are to find to complete the sequence.

The second line of each test case contains S integer numbers X1X2, ... XS separated by a space. These numbers form the given sequence. The sequence can always be described by a polynomial P(n) such that for every iXi = P(i). Among these polynomials, we can find the polynomial Pmin with the lowest possible degree. This polynomial should be used for completing the sequence.

 

Output

For every test case, your program must print a single line containing C integer numbers, separated by a space. These numbers are the values completing the sequence according to the polynomial of the lowest possible degree. In other words, you are to print values Pmin(S+1), Pmin(S+2), .... Pmin(S+C).

It is guaranteed that the results Pmin(S+i) will be non-negative and will fit into the standard integer type.

Example

Sample Input:

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

Sample Output:

7 8 9
37 46
11 56
3 3 3 3 3 3 3 3 3 3
Warning: large Input/Output data, be careful with certain languages

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>

using namespace std;

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int s,c;
		scanf("%d%d",&s,&c);
		vector<vector<int> > values;
		vector<int> x(s+c);
		bool stop=true;
		for(int i=0;i<s;i++){
			scanf("%d",&x[i]);
			if(i>0&&x[i]!=x[i-1]){
				stop=false;
			}
		}
		values.push_back(x);
		int i=0;
		while(stop==false){
			bool possible=true;
			vector<int> temp(s+c-(i+1));
			for(int j=0;j<s-(i+1);j++){
				temp[j]=(values[i][j+1]-values[i][j]>;
				if(j>0&&temp[j]!=temp[j-1]){
					possible=false;
				}
			}
			values.push_back(temp);
			stop=possible;
			if(stop==false)i++;
		}
		if(values.size()>1){
			int start=s-(i+1);
			for(int z=0;z<c;z++){
				values[i+1][start]=values[i+1][start-1];
				start++;
			}
			for(int k=i;k>=0;k--){
				int start=s-k;
				for(int m=0;m<c;m++){
					values[k][start]=values[k][start-1]+values[k+1][start-1];
					start++;
				}
			}
		}
		else{
			for(int k=s;k<s+c;k++)
				values[0][k]=values[0][k-1];
		}
		for(int k=s;k<s+c;k++){
			printf("%d",values[0][k]);
			if(k<s+c-1)printf(" ");
		}
		printf("\n");
	}
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
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

x
+
cmd
7 8 9
37 46
11 56
3 3 3 3 3 3 3 3 3 3

#2 Code Example with Java Programming

Code - Java Programming

import java.util.Arrays;
import java.util.ArrayList;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception{
		ArrayList<int[]> input = new ArrayList<>();
		ArrayList<int[]> inputlen = new ArrayList<>();
		InputStreamReader r = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(r);
		int t = Integer.parseInt(br.readLine());
		while(t > 0) {
			
			int[] serieslenparam = Arrays.stream(br.readLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();
			int[] seriesgiven = Arrays.stream(br.readLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();
			
			
			inputlen.add(serieslenparam);
			input.add(seriesgiven);
			t--;
		}
		br.close();
		r.close();
		
		for(int n = 0; n < inputlen.size(); n++) {
			int[] out = polyfill(inputlen.get(n)[0]-1, input.get(n), inputlen.get(n)[1]);
			for(int m = 0; m < out.length; m++) {
				System.out.print(out[m] + " ");				
			}
			System.out.println();
		}
	}
	
	public static int[] polyfill(int sn, int[] tempseries, int cn) {
		
		int[] outseries = new int[cn];
		
		if(sn == 0) {
			for(int i = 0; i < outseries.length; i++) {
				outseries[i] = tempseries[sn];
			}
			
			return outseries;
		}		
		
		int[] newseries = new int[tempseries.length - 1];
		int consti = 0;
		boolean flag = false;
		for(int i = 0; i < sn; i++) {			
			int sub = tempseries[i+1] - tempseries[i];
			if(i == 0) {
				consti = sub;
			}
			newseries[i] = sub;
			flag = (newseries[i] == consti) ? true : false;
		}
		if(flag == false) {
			int[] retseries = polyfill(sn - 1, newseries, cn);
			outseries[0] = tempseries[sn] + retseries[0];
			for(int m = 0; m < cn-1; m++) {
				outseries[m+1] = outseries[m] + retseries[m+1];
			}
			return outseries;
		}else {			 
			outseries[0] = tempseries[sn] + consti;
			for(int k = 0; k < cn-1; k++) {				
				outseries[k+1] = outseries[k] + consti;
			}
			return outseries;
		}
	}

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
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

x
+
cmd
7 8 9
37 46
11 56
3 3 3 3 3 3 3 3 3 3
Advertisements

Demonstration


SPOJ Solution-Complete the Sequence!-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python