什么题目啊？

动态规划测试

打包（pack.pas）
【问题描述】
你现在拿到了许多的礼物，你要把这些礼物放进袋子里。你只有一个最多装下V 体积物品的袋子，你不能全部放进去。你也拿不动那么重的东西。你估计你能拿的最大重量为 G。现在你了解了每一个物品的完美值、重量和体积，你当然想让袋子中装的物品的完美值总和最大，你又得计划一下了。
【输入格式】
第一行：V 和 G 表示最大重量和体积。
第二行：N 表示拿到 N 件礼物。
第三到N+2行：每行3个数 Ti Vi Gi 表示各礼物的完美值、重量和体积
【输出格式】
输出共一个数，表示可能获得的最大完美值。
【输入输出样例】
输入(pack.in)：
6 5
4
10 2 2
20 3 2
40 4 3
30 3 3
    输出(pack.out)：
50

【数据范围】
对于20%的数据 N，V，G，Ti，Vi，Gi≤10
对于50%的数据 N，V，G，Ti，Vi，Gi≤100
对于80%的数据 N，V，G，Ti，Vi，Gi≤300
80%到100%的数据是N，V，G，Ti，Vi，Gi≤380 的离散随机数据。

机器人搬重物(ROBOT.PAS)
【问题描叙】
机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：先前移动1步（Creep）；向前移动2步（Walk）；向前移动3步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。
【输入格式】
输入的第一行为两个正整数N,M（N,M<=50），下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有四个整数和一个大写字母，分
3
 
3别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。
【输出格式】
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1。
 

【输入样例】
ROBOT.IN
9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S
【输出样例】
ROBOT.OUT
12

尼克的任务（LIGNJA.pas）
【问题描述】
  尼克每天上班之前都连接上英特网，接受他的上司发来的邮件，这些邮件包含了尼克主管的部门当天要完成的全部任务，每个任务由一个开始时刻与一个持续时间构成。
  尼克的一个工作日为N分钟，从第一分钟开始到第N分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完成，尼克可以任选其中的一个来做，而其余的则由他的同事完成，反之如果只有一个任务，则该任务必须由尼克去完成，假如某些任务开始时刻尼克正在工作，则这些任务也由尼克的同事完成。如果某任务于第P分钟开始，持续时间为T分钟，则该任务完成需要P+T-1分钟。
【输入格式】
   输入数据第一行为整数N和K，范围都是1到1万。N表示尼克的工作时间单位为分钟，K表示任务总数。
  接下来共有K行，每一行有两个用空格隔开的整数P和T，表示该任务从第P分钟开始，持续时间为T分钟，其中1〈=P〈=N，1〈=P+T-1〈=N。
【输出格式】
   输出文件仅一行，包含一个整数，表示尼克可能获得的最大空暇时间。
【样例输入输出】
  LIGNJA.IN
15 6
1 2 
1 6
4 11
8 5
8 1
11 5
 LIGNJA.OUT
   4
动态规划优化
农田个数（Count.pas）
    你的老家在河北农村。过年时，你回老家去拜年。你家有一片N&#61620;M农田，将其看成一个N&#61620;M的方格矩阵，有些方格是一片水域。你的农村伯伯听说你是学计算机的，给你出了一道题： 他问你：这片农田总共包含了多少个不存在水域的正方形农田。
两个正方形农田不同必须至少包含下面的两个条件中的一条：
1.    边长不相等
2.    左上角的方格不是同一方格
输入
    输入数据第一行为两个由空格分开的正整数N、M（1<=m<n<=1000）
    第2行到第N+1行每行有M个数字（0或1），描述了这一片农田。0表示这个方格为水域，否则为农田（注意：数字之间没有空格，而且每行不会出现空格）
输出
    满足条件的正方形农田个数。
样例输入
    3 3
    110
    110
    000
样例输出
    5
样例说明
边长为1的正方形农田有4块
边长为2的正方形农田有1块
合起来就是5块

公路乘车（buses.pas）
【问题描叙】
   一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。
 
没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<=n<=100），它可以通过无限次的换车来完成旅程。最后要求费用最少。
输入格式
    第一行十个整数分别表示行走1到10公里的费用（<=500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。
    第二行一个整数n表示，旅客的总路程数。
输出格式
    仅一个整数表示最少费用。
样例输入
12 21 31 40 49 58 69 79 90 101
15
样例输出
147

DOLLARS(DOLLARS.PAS)
【问题描叙】
在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。
输入
输入文件的第一行是一个自然数N，1≤N≤100，表示戴维学习汇率的天数。
接下来的N行中每行是一个自然数A，1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。
输出
输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。
注意：考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。
样例
DOLLARS.IN
5
400
300
500
300
250
DOLLARS.OUT
266.66
样例解释 (无需输出)
Day 1 ... changing 100.0000 美元= 400.0000 马克
Day 2 ... changing 400.0000 马克= 133.3333 美元
Day 3 ... changing 133.3333 美元= 666.6666 马克
Day 5 ... changing 666.6666 马克= 266.6666 美元



广度优先搜索练习题

最后的迷宫
（harry.c/cpp/pas）
Time Limit:1s Memory Limit:1000k
【问题描叙】
哈利&#8226;波特作为三强争霸赛的第四名选手，历尽艰险闯到了最后一关——迷宫。
现在，迷宫里只剩下哈利和塞德里克了，哈利只有在塞德里克前面拿到奖杯，才能赢得比赛。哈利只要能看到奖杯，就可以用飞来咒拿到它，所以，现在的问题是哈利如何能尽早地看到奖杯。
哈利的视力非常好，他能从迷宫的一端沿直线看到迷宫的另一端（但他只能看八个方向——东北，东，东南，南，西南……），而且跑得非常快，跑一步（向上、下、左、右移动一格）只需要1s。但迷宫是不透光的，而且，要烧掉迷宫的墙也不容易，所以哈利决定绕到一个能够看到奖杯的地方。现在，哈利希望你能帮他确定最短需要多长时间才能拿到奖杯。
【输入格式】
输入文件harry.in第一行为2个数N，M表示迷宫的规模（N为高，M为宽）
接下来是N*M的迷宫，O表示空地，X表示墙。
最后是多对数据，分别是奖杯坐标及哈利的坐标（显然不可能在墙上），每对占一行，0为结束标志。
【输出格式】
根据每对数据，计算哈利拿到奖杯的最短时间，每对一行输出到harry.out。如果魔法部有意难为选手，用墙将奖杯包围了起来，输出”Poor Harry”。
【输入样例】
3 4
OXXO
XXOO
XOOO
3 2 2 4
3 3 1 1
0 0 0 0
【输出样例】
1
Poor Harry
数据规模
对于30%的数据,有N*M<=100
对于60%的数据,有N*M<=1600
对于100%的数据,有N*m<=16384




救援行动
（rescue.c/cpp/pas）
Time Limit:1s Memory Limit:1000k
【问题描叙】
想必大家都认识传说中的AFY，现在AFY被传说中神秘的邪恶的Moligpy人抓住了！他急需你的救援。他被关在一个迷宫中。迷宫的长、宽不超过200。 
迷宫中有不可以越过的墙以及监狱的看守。 
AFY的朋友们组织了一些救援队来到了迷宫中。他们的任务是：接近AFY。我们假设接近AFY就是到达AFY所在的位置。
假设移动（只能向上、下、左、右4个方向移动）需要1单位时间，杀死一个看守也需要1单位时间。到达一个格子以后，如果该格子有看守，则一定要杀死（否则会死的很难看的……只见那个看守开了9倍狙镜……）。交给你的任务是，计算最少要多少单位时间，才能到达AFY所在的地方？ 
【输入格式】
输入文件rescue.in第一行二个整数n，m。表示迷宫的大小为n*m。
以后n行，每行m个时字符。其中“#”代表墙，“.”表示空地，“x”表示看守，“a”表示AFY，“r”表示救援队伍。 
字母均为小写。 
【输出格式】
输出文件rescue.out只有一行，代表救出AFY的最短时间。 
如果救援小组永远不能达到AFY处，则输出“Poor AFY has to stay in the prison all his life.” 
【输入样例】
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
【输出样例】
13
数据规模
对于30%的数据，n*m<=100；
对于全部的数据，n*m<=200*200。
 
N的倍数
(multin.c/cpp/pas)
Time Limit:2s Memory Limit:30000k
【问题描叙】
写一个程序，对于给定的一个自然数N（1≤N≤4999），和M个互不相同的十进制数字X1， X2，…,XM (至少一个)． 
找出N的一个最小正的倍数，使得该倍数中没有X1，X2，…，XM 之外的其它数字。 
【输入格式】
输入文件multin.in第一行为整数N，第二行为整数 M，接下来M行 分别列出 数字 X1,X2..XM 。 
【输出格式】
输出文件multin.out输出为这个倍数，如果无解输出0。 
注：在所有的测试数据中答案都不会超过500位。 
【输入样例】
22
3
7
0
1
【输出样例】
110


信息学联赛模拟试题
题目一：精度计算（100分）    a.pas
[问题描述]
输入两个10000以内的正整数X、Y，求X除以Y的值。要求精确到小数点后100位，如果在100位内（包括100位）出现循环节，请用括号标出。如：51/7＝7.(285714)。
[输入输出]        注意：文件名写错该题得0分
输入文件：a.in
输出文件：a.out
[输入输出样例]
[样例一]
输入：（两个整数中间有一个空格，前面的数字表示X，后面的数字表示Y）
51  7  
输出：
7.(285714)
[样例二]
输入：（两个整数中间有一个空格，前面的数字表示X，后面的数字表示Y）
21  7
输出：
3

题目二：单词的划分 100分  b.pas
【问题描叙】    
有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。
【输入格式】
    从文本文件word.in中读入数据。
    第一行，一个字符串。（字符串的长度不超过100）
    第二行一个整数n，表示单词的个数。（n<=100）
    第3~n+2行，每行列出一个单词。
【输出格式】
    一个整数，表示字符串可以被划分成的最少的单词数。
【样例输入】
realityour
5
real
reality
it
your
our
【样例输出】
2
（原字符串可拆成real+it+your或reality+our，由于reality+our仅为两个部分，因此最优解为2，另外注意，单词列表中的每个单词都可以重复使用多次，也可以不用）

题目三： 最少步数（100分）    c.pas
[问题描述]
在各种棋中，一种棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将更加增加趣味性，因此，他规定马既能按“日”飞，也能各象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就和他玩一种新游戏，在围棋盘上（19*19）任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A，B两点的坐标，想知道两个位置到（1,1）点的可能最少步数。
[输入输出]        注意：文件名写错该题得0分
输入文件：c.in
输出文件：c.out
[输入输出样例]

[样例]
输入：（每行的两个整数中间有一个空格）
　　12 16    注：A点坐标
        18 10    注：B点坐标
输出：
　　8        注：A到（1,1）的可能最少步数
9        注：B到（1,1）的可能最少步数

题目四    打包   （100分）d.pas
某个工厂生产出的产品都要被打包放入正四棱柱的盒子内。所有盒子的高度都为h，但底面的尺寸不同，可以为1&#61620;1，2&#61620;2，3&#61620;3，4&#61620;4，5&#61620;5，或6&#61620;6，如图所示。
 

这些盒子将被放入高度为h，底面尺寸为6&#61620;6的箱子里，送到消费者手中。为了降低运送成本，工厂希望尽量减少箱子的数量。如果有一个好的算法，能使箱子的数量降到最低，这将给工厂节省不少资金。请你写一个这样的程序。
输入：d.in
六个非负整数a1, a2, a3, a4, a5, a6。它们分别为底面尺寸为1&#61620;1，2&#61620;2，3&#61620;3，4&#61620;4，5&#61620;5，6&#61620;6的盒子的个数。每两个数之间有一个空格。
输出：d.out
一个数B，即箱子的最少个数。
例如a1, a2, a3, a4, a5, a6分别为0, 0, 4, 0, 0, 1时，B=2；又例如a1, a2, a3, a4, a5, a6分别为7, 5, 1, 0, 0, 0时，B=1。如图所示。

 

枚举算法测试


丑数（ugly）
【问题描述】所谓丑数，就是指那些因子只含2，3，5的数。1，2，3，4，5，6，8，9，10，12，15是最前面的11个丑数。为了方便起见，把1也看作是丑数。请你编写一个程序，输入n，寻找并打印第n个丑数。
【输入数据】
输入文件仅包含一个整数n（0＜n＜3000）。
【输出数据】
输出文件仅包含一个整数，表示所求的第n个丑数。
【样例】
ugly.in
11

ugly.out
15


完全平方数（number）
【问题描述】由1～9九个数字组成的全排列可以被看作是一个九位数，编程求出这些九位数中第n个完全平方数（按九位数从小到大排序）。
【输入数据】
输入文件仅包含一个整数n，表示要求的完全平方数的序号。
【输出数据】
输出文件仅包含一个九位数。
【样例】
number.in
6

number.out
254817369



等差数列（aseq）
【问题描述】
给定n(1<=n<=5000)个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度.
【输入数据】
第一行是一个整数n,接下来一行包括了n个数,每个数的绝对值不超过10000000.
【输出数据】
对于每个输入数据,输出你所找出的最长等差数列的长度
输入样例
Aseq.in
7
3
8
4
5
6
2
2
输出样例
Asep.out
5

深度优先搜索
放书(bf)
【问题描叙】
N本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？
【输入格式】
输入文件bf.in只有一个正整数N（1<=N<=50）
【输出格式】
输出文件bf.out只有一个正整数，表示有多少种摆放方法。
【输入样例】
2
【输出样例】
1

安排工作（job）
【问题描叙】
现在有N人从事N项工作N项工作每人胜任每项工作的效率值给大家，求总效率最高？
例如有A,B,C,D,E 5人从事j1,j2,j3,j4,j5   
 5项工作每人只能从事一项,它们的效益表如下:
　    j1    j2    j3    j4    j5
A    13    11    10    4    7
B    13    10    10    8    5
C    5    9    7    7    4
D    15    12    10    11    5
E    10    11    8    8    4
求最佳安排,使效益最高.
【输入格式】
输入文件job.in共有N+1行，第一行为N（1<=N<=10）表示有多少人，后面每行有N个数，表示每人胜任每项工作的效率是多少。
【输入格式】
输出文件job.out只有一行表示总效率的最大值。
【输入样例】
2
2 2
3 4
【输出样例】
6



骑士游历限制版（kinght）
【问题描叙】
设有一个m×n的棋盘(2≤m≤30  2≤n≤30)，在棋盘上任一点有一个中国象棋“马”，马走的规则为：马走日字；马只能向右走。当m,n给出后，同时给出马起始的位置和终点的位置，试找出从起点到终点所有路径的数目。
【输入格式】
输入文件kinght.in只有一行包含m,n,x1,y1,x2,y2 
(分别表示m,n、起点坐标和终点坐标)
【输出格式】
    输出文件kinght.out只有一个路径数目（若不存在，则输出0）
【输入样例】
2 2 1 1 2 2
【输出样例】
0
树和图的测试

孪生蜘蛛 (spider.pas）
在G城保卫战中，超级孪生蜘蛛Phantom001和Phantom002作为第三层防卫被派往守护内城南端一带极为隐秘的通道。
根据防护中心的消息，敌方已经有一只特种飞蛾避过第二层防卫，直逼内城南端通道入口。但优秀的蜘蛛已经在每个通道内埋下了坚固的大网，无论飞蛾进入哪个通道，他只有死路一条！（因为他是无法挣脱超级蛛网的）
现在，001和002分别驻扎在某两个通道内。各通道通过内线相通，通过每条内线需要一定的时间。当特种飞蛾被困某处，001或002会迅速赶来把它结果掉（当然是耗时最少的那个）。
001跟002都想尽早的完成任务，他们希望选择在最坏情况下能尽早完成任务的方案。
输入：
第一行为一个整数N (N<=100) 表示通道数目。
接下来若干行每行三个正整数a,b,t 表示通道a,b有内线相连，通过的时间为t。(t<=100)
（输入保证每个通道都直接/间接连通）
输出：
两个不同的整数x1,x2，分别为001，002驻扎的地点。（如果有多解，请输出x1最小的方案，x1相同则输出x2最小的方案）
样例：
spider.in
3
1 2 5
2 3 10
3 1 3
spider.out
1 2

截断通路 (sever.pas)
苏联在天才总书记天凯的带领下，迅速发展，一片欣欣向荣之势。
经过一个星期的努力，苏联已经兴建起了n多道路，这使得想对其进行轰炸的美帝国感到十分的不爽。好战的美帝国头头LYNN制定了初步的攻击计划：切断苏联两个重镇之间的联系（也就是使这两城之间没有通路）。他们掌握了苏联道路的准确情况，并估算出轰炸一条道路所需的耗费。
现在，请你计算出切断s,t两城之间联系的最少耗费。(双向边)
输入：
第一行包含三个整数，分别为N,S,T。（N<=100）
接下来的若干行每行包含三个正整数a,b,c。分别表示城市a,b之间有道路相连，摧毁这条道路的耗费为c (c<=100)。

输出：
一个整数：最少耗费。
样例：
sever.in
3 1 3
1 2 1
2 3 2
sever.out
1

探案第二部 (holmes.pas)
我们伟大的 Sherlock&#8226;Holmes 先生最近遇上了一件相当棘手的案子，随着对案情逐渐深入的研究，他开始意识到：此案地域横跨欧洲，而起因可以追溯到50年前！为了尽快搜集各方面的线索，他决定与Dr. Watson分头行动。
Holmes列出了若干需要的线索：某处的一些雪茄烟灰；地下室油画上的颜料的呈色；Black兄弟与他们邻里的联系……诸如此类。而搜集这些线索需要一定的时间。不过，有些线索是相关联的，即在得到某个线索的时候，一并可以得出其他结论（我们可以认为这是不需要时间的）
    请充分相信Holmes先生！他无比敏锐的思维足够将所有线索串联，以完美的推理侦破这件名噪一时的大案！

输入：
第一行为N，表示N个需要搜集的线索(N<=1000)
接下来N行，每行两个整数ai,bi, 分别表示Holmes，Watson搜集第i个线索所需要的时间。（ai,bi<=15）
接下来若干行，每行两个整数x,y，表示得到x, 同时能够得到y。

输出：
一个整数，即搜集所有线索的最小耗时。

样例：
holmes.in
2
5 6
3 9
1 2
holmes.out
5
数学问题研究测试
 
公式变形（formula）
【问题描叙】
在数理化中常遇到公式变形，先让我们考虑最简单的一种。
公式定义为：左边=右边
左边，右边为一些大些字母与+，-(无括号)组成的式子，每一个大写字母为一个变量，在公式中最多出现一次。
【输入格式】
输入文件formula.in有两行，其中第一行为公式，第二行为目标变量。
【输出格式】
输出文件formula.out仅一行为目标变量对应的表达式，各个变量要按字母排序（小的在前），第一个‘+’不可省略。
【输入样例】
P=A+C-M
C
【输出样例】
-A+M+P

整数分解(givensum)
【问题描述】
一个正整数有可能可以被表示为n(n>=2)个连续正整数之和，如：
15=1+2+3+4+5
15=4+5+6
15=7+8
请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。
【输入格式】
输入文件givensum.in包含一个正整数N（1<N<1010）。
【输出格式】
输出文件givensum.out第一行为整数k,表示解的组数，剩余k行每行两个数字，分别表示组成N的连续数字和的第一个正整数和最后一个正整数，而且k组解是按照各组解第一个正整数从小到大排列的；如果无解，则输出给定的正整数N。
【输入样例】
10000
【输出样例】
4
18 142
297 1328
388 412
1998 2002




完全数(perfect)
【问题描述】 
正整数n的所有小于n的不同正因数之和若等于n本身，称数n为完全数。
例如，6的正因数为1,2，3，而6=1=2+3，则6是一个完全数。
试找出a～b之间的完全数。
【输入格式】
输入文件perfect.in包含一行两个正整数a和b,表示求的范围（1≤a,b≤1020）
【输出格式】 
输出文件perfect.out包含如干行，表示在这个区域的完全数及其算式。
若找不到，则输出“No Answer!”。 
【样例输入1】 
6  29
【样例输出1】
6=1+2+3
28=1+2+4+7+14
【样例输入2】
7  8
【样例输出2】
No Answer!

贪心算法


题目名称    集合删数    d-规则问题    射击竞赛
提交程序
( PAS / CPP)    number.pas
number.cpp    drule.pas
drule.cpp    sho.pas
sho.cpp
输入文件    number.in    Drule.in    Sho .in
输出文件    number.out    Drule.out    sho.out
内存限制    32MB    32MB    32MB


问题A:　 集合删数
问题描述：
一个集合有如下元素：1是集合元素；若P是集合的元素，则2 * P +1，4*P+5也是集合的元素，取出此集合中最小的K个元素，按从小到大的顺序组合成一个多位数，现要求从中删除M个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。
注：不存在所有数被删除的情况`
输入格式：
输入的仅一行，K，M的值，K，M均小于等于30000。
输出格式：
输出为两行，第一行为删除前的数字，第二行为删除后的数字。
样例输入：
5  4
样例输出：
137915
95

问题B:　 d-规则问题
问题描述：

对任意给定的m(m∈N+)和n(n∈N+)，满足m<n，构造一初始集合：P={x|m≤x≤n,x∈N+}(m,n≤100)。现定义一种d规则如下：若存在a∈P，且存在K∈N+ ,K>1，使得K&acute;a∈P，则修改P为：P=P-{y|y=s&acute;a,s∈N+ } ，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。 
输入格式：
    输入仅一行，M,N的值。
输出格式：
    输出每次使用d规则时的分值和集合p的变化过程(即变化后的集合内所有的数,每个数用空格隔开),注意D后面有个空格，冒号后面有个空格。如果没有一次可以变化就输出0。
样例输入：
(1)
    1 10
(2)
    56 57
样例输出：
(1)
5 : 1 2 3 4 6 7 8 9
4 : 1 2 3 6 7 9
2 : 1 3 7 9
3 : 1 7
1 :
(2)
0


问题C  PROBLEM:  SHO（射击竞赛）
欢迎来参加年度的BYTELAND射击竞赛。每个参赛者的射击目标是一个矩形网格。目标由R×C个小方格组成，分别为R行，C列。小方格被涂成白色或黑色。每一列恰有2个白色的小方格和R－2个黑色的小方格。行从顶至底编号依次为1，…，R，列从左至右编号依次为1，…，C。射击者可射击C次。
在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。
请帮助射击者找到一种正确的射击法，若这样的射击法存在。
例子：
考虑以下目标：
 
 一连串的射击分别击中第1列的第2列，第2列的第3列，第3列的第1行，第4列的
第4行，这种射击方法是正确的。
任务：
写一个程序：
&#61548;    从文件SHO.IN中读出数据的组数；每组包括针对这一问题的一套数据。
&#61548;    对每组数
&#61618;    读取目标的大小和白色方格的设置；
&#61618;    证明是否存在正确的射击方法，若存在，请找出一种；
&#61618;    将结果写至文件SHO.OUT上。
【输入格式】
输入文件SHO.IN:的第一行包括数据的组数X，1≦X≦5，接下来的行由X组组成。第一组从该文件第二行开始，其它各组依次直接接在前一组之后。
每组的首行包括两个整数R和C，被一空格隔开，2≦R≦C≦1000，这分别是矩形网格的行数和列数。该组中接下来的C行，每行包括两个整数，被一空格隔开。每组中的第I+1行的整数（1≦    I≦C），是第I列中白色方格所在的行的标号。
【输出格式】
输出文件SHO.OUT对第I组，1≦I≦X，你的程序应将以下内容写至文件SHO.OUT中；或者是由对白色方格的正确的一连串射击，形成的一个由C个行号组成的序列（中间均由1个空格隔开），即在列1，2，…，C上依次被击中的白色方格的行号，或者若不存在这样一种正确的射击法，写上单词NO。
示例：
【输入样例】
2
4 4
2 4
3 4
1 3
1 4
5 5
1 5
2 4
3 4
2 4
2 3
【输出样例】
2 3 1 4
NO

难啊

LZ强悍。。哪里来这么多提