2008年ACM工大题.docVIP

子集问题 问题描述： 子集的一个实例为（S，c）。其中，S={x1，x2，、、、、、、、，xn}是n个正整数的集合， C是一个正整数。子集问题要求找出所有满足条件子集S1，使得，试设计一个解子集的算法。 输入： 输入包括一个或测试用例。每个测试用例包括2行，第1行有2个正整数n和c, n表示S的大小，c是子集的目标值。接下来的1行中，有n个正整数，表示集合S的元素。当一个测试用例的第1行为2个0时，输入结束，而且该测试用例不必处理。 输入： 对每个测试用例，输入也是2行，第一行为一个正整数m,表示满足条件的自集个数， 第2行为满足条件的子集列表，每个子集用（）括号括起来，元素间空格间隔，当测试每个测试用例的输入结果之间有一空行，最后一个没有空行。 输入示例： 10 3 5 6 7 30 3 4 6 7 0 输出示例： 2 7） （2 3 5） No solution! 2, 超长数字串问题 问题描述： 给定一个数字串S：12345678910111213141516171819202122232425262728、、、、、、，它是有所有自然数从小到大依次排序起来的。任意给定一个数字串S1，它一定在S中出现无穷多次，编程求出它的第一次出现的位置。 输入： 输入包括一个或多个测试用例。每个测试用例包括1行，每行有一个子串。当一个测试用例的内容为-1时，输入结束，而且该测试用例不必处理。 输出： 对每个测试用例，输入一个m，表示对应子串在S中第一次出现的位置，每个测试用例的输出结果之间有一空行，最后一个没有空行。 输入示例： 81 222 -1 输出示例： 27 34 排列问题 问题描述： 在整数1，2，、、、、，N的排列中，有些排列满足性质A：该排列所构成的整数可被3整除。例如：N=3，排列123，231是具有A的，而N=4时，4213则不满足性质A。 输入： 输入包括一个或多个测试用例。每个测试用例包括行，每行有一个N。当一个测试用例的内容为-1时，输入结束，而且该测试用例不必处理。 输出： 对每个测试用例，输入多行，其中第一行输入一个正整数m，表示对应排列中满足A的排列数目，接下来的m行是满足性质A的排列列表，每个测试用例的输入结果之间有一空行，最后一个没有空行。 输入示例： 3 2 -1 输出示例： 6 123 132 213 231 312 321 2 12 21 求最长子串问题 问题描述： 给定N个字符串，找出它们的最长的子串。 输入： 输入的第一行为一个整数N，（2=N=20）,接下来有N行，每行为一个字符串，每个字符串的长度均小于255 输入示例： 3 This is a Big World. Oh, this is Fruit DLfijewfiawhthis I fevaw 输出示例： his i 5.报数问题 问题描述： 有M个人围成一圈，顺序排号，从第一个开始顺序报数（从1到N），凡报到N的退出圈子。退出者的下一个人有从1开始报数，直到圈子里只剩下一个人。请你编写一个程序找出最后一个留在圈子里的人原来的序号。 输入： 输入文件包括多组测试数据。第一行为一个整数C，表示有C组测试数据，接下来有C行数据，每组测试数据只占行，每行有2个整数，它们用空格隔开，第一个整数表示开始的人数M（1=M=200）,第二行整数表示报数的最大数N（1=N=30000） 输出： 你的输出应该有C行，即每组测试数据的输出占一行，它是一个整数，表示最后一个留在圈子里的人原来的序号。 输入示例： 3 3 15 2 输出示例 13 1 3 6．拦截导弹 问题描述： 某国为了防御敌国导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷；虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能超过前一发的高度。某天，雷达扑捉到敌国来袭由于该系统还在使用阶段，所以只有一套系统，因此有可能不能拦截所有不能拦截所有的导弹。 输入：输入若干组数据，每组数据包；导弹总个数（正整数），导弹此次飞来的高度（高度数据均是不大于30000的正整数，用空格分割） 输出： 对应每组数据有一行输入，是这套系统最多能拦截的导弹数。 输入示例： 8 389 207 155 300 299 170 158 65 输出示例： 6 7．畅通工程 问题描述： 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相通，只要相互能间接到达即可）。问最少还需要设多少条道路？ 输入： 测试输入包括若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N（〈1000）和道路数