文理学院程序设计在线练习


最大素数环

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 137   Accepted Submission(s): 62
Problem Description

小学数学有类似这样的题目: 把1~6这6个数排成一排,使任意2个相邻的数之和为素数(要求队首和队尾2数之和也是素数),问你一共有多少种不同的排法。

对你来说,这样的题目显然没有任何挑战性可言。因此,我们作一变化:我们要求在1~n这n个数选择k个数排成一排。(2<=n<=22, 2<=k<=10),当然,仍然要求任意2个相邻的数之和为素数(包括首尾)。

请你计算符合要求的排列总数共有多少种,并计算符合要求的k个数的最大和。
若无法满足要求,请分别输出0 0。

例如: n=4,k=4时
1->2->3->4(->1) 和为10
1->4->3->2(->1) 和为10
2->1->4->3(->2) 和为10
2->3->4->1(->2) 和为10
3->4->1->2(->3) 和为10
3->2->1->4(->3) 和为10
4->1->2->3(->4) 和为10
4->3->2->1(->4) 和为10
最大和为10

例如: n=10,k=6时
10->9->8->5->6->7(->10) 和为45
1->2->3->4->7->6(->1) 和为23
......(以下省略)
最大和为45

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据。(1<=T<=30)
对于每组测试数据,第一行是2个正整数,分别表示n和k(2<=n<=22 , 2<=k<=10)。

Output

对于每组测试,请你计算符合要求的排列总数共有多少种,并输出符合要求的k个数的最大和。
若无法满足要求,请分别输出0 0。
Sample Input
3
4 4
10 6
4 5
Sample Output
8 10
672 45
0 0
Author

flx

Source

绍兴文理学院第五届程序设计竞赛2011/03/27