Output
一个正整数，表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod10000的值。
SampleInput
15
SampleOutput
129
7、平方数
给出包含M个数字的列表，和列表中所有数字的所有质因数。
求出最长的子列表，使得子列表中所有数字的乘积是一个完全平方数。
输入
输入文件包含多组测试数据。
第一行包含两个整数N,M（1<=N<=30,1<=M<=30000）.N是质因数的个数。
接下来一行有N个整数，给出所有的质因数。
然后一行包含M个整数，给出列表。
输入文件结束于N=M=0.
输出
对于每组数据，输出最长子列表的两个位置坐标lr。
l是该子列表在列表中的起始位置，r是结束位置。
如果多种情况都满足子列表长度最大，输出l最小的一个。
如果不存在这样的子列表输出“None”。
样例输入
34
235
49256
34
235
6633
00
样例输出
13
14
8、跳蚤
Description
Z城市居住着很多只跳蚤。
在Z城市周六生活频道有一个娱乐节目。
一只跳蚤将被请上一个高空钢丝的正中央。
钢丝很长，可以看作是无限长。
节目主持人会给该跳蚤发一张卡片。
卡片上写有N+1个自然数。
其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。
跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。
而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。
比如当N=2，M=18时，持有卡片（10,15,18）的跳蚤，就可以完成任务：
他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。
而持有卡片（12,15,18）的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。
当确定N和M后，显然一共有M^N张不同的卡片。
现在的问题是，在这所有的卡片中，有多少张可以完成任务。
Input
两个整数N和M（N<=15,M<=100000000）。
Output
可以完成任务的卡片数。
SampleInput
24
SampleOutput
12
Hint
这12张卡片分别是：
（1,1,4）,（1,2,4）,（1,3,4）,（1,4,4）,（2,1,4）,（2,3,4）,
（3,1,4）,（3,2,4）,（3,3,4）,（3,4,4）,（4,1,4）,（4,3,4）
9、蛇行矩阵
Problem
蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。
Input
本题有多组数据，每组数据由一个正整数N组成。
（N不大于100）
Output
对于每一组数据，输出一个N行的蛇形矩阵。
两组输出之间不要额外的空行。
矩阵三角中同一行的数字用一个空格分开。
行尾不要多余的空格。
SampleInput
5
SampleOutput
1361015
25914
4813
712
11
10、滑雪
Description
Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。
可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。
Michael想知道载一个区域中最长底滑坡。
区域由一个二维数组给出。
数组的每个数字代表点的高度。
下面是一个例子
12345
161718196
152425207
142322218
131211109
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。
在上面的例子中，一条可滑行的滑坡为24-17-16-1。
当然25-24-23-...-3-2-1更长。
事实上，这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C（1<=R,C<=100）。
下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
SampleInput
55
12345
161718196
152425207
142322218
131211109
SampleOutput
25
11、采药
【问题描述】
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。
为此，他想拜附近最有威望的医师为师。
医师为了判断他的资质，给他出了一个难题。
医师把他带到一个到处都是草药的山洞里对他说：
“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
我会给你一段时间，在这段时间里，你可以采到一些草药。
如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。
”
如果你是辰辰，你能完成这个任务吗？
【输入文件】
输入文件medic.in的第一行有两个整数T（1<=T<=1000）和M（1<=M<=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【样例输入】
703
71100
691
12
【样例输出】
3
【数据规模】
对于30%的数据，M<=10；
对于全部的数据，M<=100。
12、取石子游戏
Description
有两堆石子，数量任意，可以不同。
游戏开始由两个人轮流取石子。
游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。
最后把石子全部取完者为胜者。
现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
Input
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。
Output
输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。
SampleInput
21
84
47
SampleOutput
0
1
0
13、滑雪
Description
Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。
可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。
Michael想知道载一个区域中最长底滑坡。
区域由一个二维数组给出。
数组的每个数字代表点的高度。
下面是一个例子
12345
161718196
152425207
142322218
131211109
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。
在上面的例子中，一条可滑行的滑坡为24-17-16-1。
当然25-24-23-...-3-2-1更长。
事实上，这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C（1<=R,C<=100）。
下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
SampleInput
55
12345
161718196
152425207
142322218
131211109
SampleOutput
25
14、敲七
Problem
输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）
Input
一个整数N。
（N不大于30000）
Output
从小到大排列的不大于N的与7有关的数字，每行一个。
SampleInput
20
SampleOutput
7
14
17
15、埃及分数
Problem
在古埃及，人们使用单位分数的和（形如1/a的,a是自然数）表示一切有理数。
如：
2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。
对于一个分数a/b,表示方法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
如：
19/45=1/3+1/12+1/180
19/45=1/3+1/15+1/45
19/45=1/3+1/18+1/30,
19/45=1/4+1/6+1/180
19/45=1/5+1/6+1/18.
最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。
给出a,b（0〈a〈b〈1000）,编程计算最好的表达方式。
Input
第一行:
N表示有N组测试数据，每组测试数据为一行包含a,b（0〈a〈b〈1000）。
Output
每组测试数据若干个数，自小到大排列，依次是单位分数的分母。
SampleInput
1
1945
SampleOutput
5618
16、炮兵阵地
Description
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。
一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H"表示），也可能是平原（用"P"表示），如下图。
在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：
沿横向左右各两格，沿纵向上下各两格。
图上其它白色网格均攻击不到。
从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符（'P'或者'H'），中间没有空格。
按顺序表示地图中每一行的数据。
N<=100；M<=10。
Output
仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
SampleInput
54
PHPP
PPHH
PPPP
PHPP
PHHP
SampleOutput
6
18、整数划分问题
整数划分是一个经典的问题。
希望这道题会对你的组合数学的解题能力有所帮助。
Input
每组输入是两个整数n和k。
（1<=n<=50,1<=k<=n）
Output
对于每组输入，请输出六行。
第一行：
将n划分成若干正整数之和的划分数。
第二行：
将n划分成k个正整数之和的划分数。
第三行：
将n划分成最大数不超过k的划分数。
第四行：
将n划分成若干奇正整数之和的划分数。
第五行：
将n划分成若干不同整数之和的划分数。
第六行：
打印一个空行。
SampleInput
52
SampleOutput
7
2
3
3
3
Hint:
1、将5划分成若干正整数之和的划分为：
5,4+1,3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1
2、将5划分成2个正整数之和的划分为：
3+2,4+1
3、将5划分成最大数不超过2的划分为：
1+1+1+1+1,1+1+1+2,1+2+2
4、将5划分成若干奇正整数之和的划分为：
5,1+1+3,1+1+1+1+1
5、将5划分成若干不同整数之和的划分为：
5,1+4,2+3
19、谁拿了最多奖学金
Problemdescription
某校的惯例是在每学期的期末考试之后发放奖学金。
发放的奖学金共有五种，获取的条件各自不同：
1）院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或1篇以上论文的学生均可获得；2）五四奖学金，每人4000元，期末平均成绩高于85分（>85），并且班级评议成绩高于80分（>80）的学生均可获得；3）成绩优秀奖，每人2000元，期末平均成绩高于90分（>90）的学生均可获得；4）西部奖学金，每人1000元，期末平均成绩高于85分（>85）的西部省份学生均可获得；5）班级贡献奖，每人850元，班级评议成绩高于80分（>80）的学生干部均可获得；只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。
例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。
现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。
Input
输入的第一行是一个整数N（1<=N<=100），表示学生的总数。
接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。
姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。
每两个相邻数据项之间用一个空格分隔。
Output
输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。
如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。
第三行是这N个学生获得的奖学金的总数。
SampleInput
4
YaoLin8782YN0
ChenRuiyi8878NY1
LiXin9288NN0
ZhangQin8387YN1
SampleOutput
ChenRuiyi
9000
28700
20、破解平方数
Problem
给出m个数b1,b2,...,bm,每个数的素数因子都在前t个素数之内，任务是寻找这m个数的非空子集的个数x，使得每个子集的乘积都是一个完全平方数。
例如t=3,则前3个素数为2,3,5。
m=4，这4个数为9,20,500,3，每个数的素因子都是在前3个素数内，则有x=3个非空子集合{9}，{20，500}，{9，20，500}，满足每个集合内的数的乘积是一个完全平方数，输出这样的集合的个数。
Input
每组测试数据的第一行为两个正整数t,m（1≤t≤100,1≤m≤100）第二行为m个数，1<=bi<=109处理至文件结束
Output
每行输出一个整数x，对应每组测试数据
SampleInput
34
9205003
SampleOu
升级会员 