亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Complete the Sequence[HDU1121]

系統 2374 0

Complete the Sequence

Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 202????Accepted Submission(s): 119

Problem Description
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.n^2-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.n^D+aD-1.n^D-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. 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 X1, X2, ... 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 i, Xi = 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.

?

?

?

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
?

?

Source
Central Europe 2000
?

?

Recommend
JGShining

不斷兩兩作差直到全部相等或只剩一個元素,之后遞推求解.

      #include<stdio.h>

int y[200][200];

int S,C;

bool finish(int x)

{

	int i;

	for (i=1+x;i<S;i++)

		if (y[x][i]!=y[x][i+1]) return false;

	return true;

}

int main()

{

	int T,i,j;

	scanf("%d",&T);

	while (T--)

	{

		scanf("%d%d",&S,&C);

		for (i=1;i<=S;i++) scanf("%d",&y[0][i]);

		int D=0;

		while (!finish(D))

		{

			D++;

			for (i=1+D;i<=S;i++) y[D][i]=y[D-1][i]-y[D-1][i-1];

		}

		for (i=1;i<=C;i++) y[D][S+i]=y[D][S+i-1];

		for (i=D-1;i>=0;i--)

			for (j=1;j<=C;j++)

				y[i][S+j]=y[i][S+j-1]+y[i+1][S+j];

		for (i=1;i<C;i++) printf("%d ",y[0][S+i]);

		printf("%d\n",y[0][S+C]);

	}

	return 0;

}


    

?

Complete the Sequence[HDU1121]


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 日韩成人精品在线 | 在线中文字幕观看 | 九九热精品免费 | 久青草免费视频手机在线观看 | 888午夜不卡理论久久 | 国产精品成人免费视频 | 亚洲天堂一区二区 | 免费黄色一级网站 | 色偷偷91久久综合噜噜噜噜 | 香蕉精品视频在线观看入口 | 亚洲图片欧美日韩 | 欧美日本一区亚洲欧美一区 | 欧美特黄级乱色毛片 | 久久亚洲精品人成综合网 | 国产大片中文字幕在线观看 | 久久爱avwww久久爱 | 九九热精品视频在线观看 | 亚洲精品国产福利在线观看 | 久久国产精品夜色 | 亚洲美女视频在线观看 | 毛片爱做的片 | 免费一级欧美大片久久网 | 欧美成人禁片在线www | 日韩毛片基地一区二区三区 | 国产精品一区二区三区四区 | 在线日韩麻豆一区 | 狠狠色香婷婷久久亚洲精品 | 久久91精品国产91久久户 | 国产精品视频麻豆 | 久久精品五月天 | 亚洲欧洲久久久精品 | 九九99热久久精品在线6手机 | 成人影院在线观看 | 老色99久久九九精品尤物 | 国产欧美亚洲精品综合在线 | 久久精品国产国产 | 亚洲欧美综合图区官网 | 四虎影视永久在线观看 | 中文字幕精品在线视频 | 97se亚洲国产综合自在线观看 | 国产乱码精品一区二区三区卡 |