ACM_习题集.doc

Sorting It All OutDescriptionAn ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A B, B C and C D. in this problem, we will give you a set of relations of the form A B and ask you to determine whether a sorted order has been specified or not. InputInput consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 = n = 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.OutputFor each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined after xxx relations: yyy.y. Sorted sequence cannot be determined. Inconsistency found after xxx relations. where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy.y is the sorted, ascending sequence. 输入样例 4 6ABACBCCDBDAB3 2ABBA26 1AZ0 0输出样例 Sorted sequence determined after 4 relations: ABCD.Inconsistency foundRun Length EncodingDescription Your task is to write a program that performs a simple form of run-length encoding, as described by the rules below. Any sequence of between 2 to 9 identical characters is encoded by two characters. The first character is the length of the sequence, represented by one of the characters 2 through 9. The second character is the value of the repeated character. A sequence of more than 9 identical characters is dealt with by first encoding 9 characters, then the remaining ones. Any sequence of characters that does not contain consecutive repetitions of any characters is represented by a 1 character followed by the sequence of characters, terminated with another 1. If a 1 appears as part of the sequence, it is escaped with a 1, thus two 1 characters are output. Input The input consists of letters (both upper- and lower-case), digits, spaces, and punctuation. Every line is terminated with a newline character and no other characters appear in the input. Output Each line in the input is encoded separately as described above. The newline at the end of each line is not encoded, but is passed directly to the output. 输入样例 AAAAAABCCCC12344输出样例 6A1B14C11123124 after 2 relations.Sorted sequence cannot be determined.百度语言翻译机2006 年百度之星程序设计大赛初赛题目 6 百度语言翻译机 时限 1s 百度的工程师们是非常注重效率的，在长期的开发与测试过程中，他们逐渐创造了一套他们独特的缩率语。他们在平时的交谈，会议，甚至在各中技术文档中都会大量运用。 为了让新员工可以更快地适应百度的文化，更好地阅读公司的技术文档，人力资源部决定开发一套专用的翻译系统，把相关文档中的缩率语和专有名词翻译成日常语言。 输入数据： 输入数据包含三部分 1. 第一行包含一个整数 N （ N=10000 ），表示总共有多少个缩率语的词条。 2. 紧接着有 N 行的输入，每行包含两个字符串，以空格隔开。第一个字符串为缩率语（仅包含大写英文字符，长度不超过 10 ），第二个字符串为日常语言（不包含空格，长度不超过 255 ） . 3. 从第 N+2 开始到输入结束为包含缩略语的相关文档。（总长度不超过 1000000 个字符） 输出数据： 输出将缩率语转换成日常语言的文档。（将缩率语转换成日常语言，其他字符保留原样） 输入样例 6 PS 门户搜索部 NLP 自然语言处理 PM 产品市场部 HR 人力资源部 PMD 产品推广部 MD 市场发展部 百度的部门包括 PS ， PM ， HR ， PMD ， MD 等等，其中 PS 还包括 NLP 小组。 输出样例 百度的部门包括门户搜索部，产品市场部，人力资源部，产品推广部，市场发展部等等，其中门户搜索部还包括自然语言处理小组。注意： 1 输入数据中是中英文混合的，中文采用 GBK 编码。 2 为保证答案的唯一性，缩率语的转换采用正向最大匹配（从左到右为正方向）的原则。请注意输入例子中 PMD 的翻译。 座位调整2006 年百度之星程序设计大赛初赛题目 5 座位调整 题目描述： 百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。 调整的方法如下： 1 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。 2 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。 3 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。 数据输入： 第一行包含两个整数 N ， M ，（ 1=N ， M=300 ）。分别表示 N 个区域和 M 个员工。 第二行是 N 个整数构成的数列 a ，其中 ai 表示第 i 个区域可以容纳的员工数， (1=ai ”和“ ”，分别表示和局、第一个小孩胜和第二个小孩胜三种情况。 输出格式： 每组测试数据输出一行，若能猜出谁是裁判，则输出身为裁判的小孩的编号，并输出在第几次游戏结束后就能够确定谁是裁判。如果无法确定谁是裁判，或者发现剪刀石头布游戏的胜负情况不合理（即无论谁是裁判都会出现矛盾），则输出相应的信息。具体输出格式请参考输出样例。 输入样例 3 3 01 12 20 3 5 01 12 02 4 4 01 23 1 0 输出样例 Can not determine Player 1 can be determined to be the judge after 4 lines Impossible Player 0 can be determined to be the judge after 0 lines 说明： 共有 5 个测试数据集，每个测试数据集为一个输入文件，包含多组测试数据。每个测试数据集从易到难分别为 5 、 10 、 15 、 30 和 40 分，对每个测试数据集分别执行一次程序，每次必须在运行时限 3 秒内结束程序并输出正确的答案才能得分。 所有数据均从标准输入设备（ stdin/cin ）读入，并写出到标准输出设备 （ stdout/cout ）中。 五个测试数据集中输入 N 分别不大于 20 、 50 、 100 、 200 和 500 ，各有 10 组测试数据。 变态的比赛规则2006 年百度之星程序设计大赛初赛题目 3 变态的比赛规则 为了促进各部门员工的交流，百度 (baidu) 举办了一场全公司范围内的 拳皇友谊赛 ，负责组织这场比赛的是百度的超级 拳皇 迷 W.Z. W.Z 不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。 由于一些员工（比如同部门或者相临部门员工）平时接触的机会比较多，为了促进不同部门之间的交流， W.Z 希望员工自己组成不同组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人则之间不会打任何比赛。 比如 4 个人，编号为 1-4, 如果分为两个组并且 1,2 一个组， 3 ， 4 一个组，那么一共需要打四场比赛： 1 vs 3,1 vs 4,2 vs 3,2 vs 4. 而如果是 1,2,3 一组， 4 单独一组，那么一共需要打三场比赛 : 1 vs 4,2 vs 4,3 vs 4. 很快 W.Z 意识到，这样的比赛规则可能会让比赛的场数非常多。 W.Z 想知道如果有 N 个人 , 通过上面这种比赛规则，总比赛场数有可能为 K 场吗？比如 3 个人，如果只分到一组则不需要比赛，如果分到两组则需要 2 场比赛 , 如果分为三组则需要 3 场比赛。但是无论怎么分都不可能只需要 1 场比赛。 相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助 W.Z 吧。 输入 每行为一组数据，包含两个数字 N, K 。 (0N=0) 输出 对输入的 N,K 如果 N 个员工通过一定的分组方式可能会一共需要 K 场比赛，则输出 YES, 否则输出 NO, 每组数据占一行。 所有的输入输出均为标准输入输出。 例子 输入样例 2 0 2 1 3 1 3 2 输出样例 YES YES NO YES 蝈蝈式的记分2006 年百度之星程序设计大赛初赛题目 2 题目名称：蝈蝈式的记分 内容描述： 蝈蝈小朋友刚刚学会了 0-9 这十个数字 , 也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高，于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了，比如用“ 3 2 4 ” 可以表示一方在这一局中连得三分后，输了两分，接着又连得到四分。可是，后来大人们发现蝈蝈只会用 0-9 这十个数字，所以当比赛选手得分超过 9 的时候，他会用一个 X 来表示 10 完成记分。但问题是，当记录为“ X 3 5 ” 的时候，蝈蝈自己也记不起来是一方连续得到十三分后，再输五分；还是先赢十分输三分再赢五分。 因为百度内部就要开始进行羽毛球联赛了，要先摸清大家的实力才好分组比赛呢于是，大人们想知道以前每局的比分是怎样的，以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛进程的情况，也要输出相应的提示哦。 需要帮蝈蝈进一步说明的是，比赛是五局三胜的，每局先获得二十一分的为胜，但是胜方必须领先对手两分或以上，否则必须继续比赛直到一方超出对手两分为止，比分多的一方获胜。任何一方先获得三局的胜利后就获得胜利，比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。 输入数据： 以 point.in 为输入文件，文件中首行只有一个整数 M ，表示蝈蝈记录了多少场比赛的分数。每场比赛用两行记录，第一行是一个整数 N(N=1000) 表示当前这个记录中有多少个字符，第二行就是具体的 N 个字符表示记录的分数。 输出数据： 相应的内容将输出到 point.out 文件中，对应每一个分数记录，输出相应的每局分数，每局分数都使用两个整数表示，表示两个选手的得分，中间用 : 分隔开；每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测的时候，以” Unknown “一个单词独占一行表示。 输入和输出结果数据样例： 输入样例 3 23 9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X 1 X 1 1 25 9 3 8 5 4 8 3 9 8 4 X X X X 2 X X X X 2 8 4 9 2 4 43 7 7 7 7 7 3 4 5 6 7 6 5 4 2 1 3 5 7 9 7 5 3 1 3 0 9 9 3 9 3 2 1 1 1 5 1 5 1 5 1 5 5 1 输出样例 21:17 24:22 21:3 Unknown 21:14 20:22 21:23 21:16 21:9 饭团的烦恼2006 年百度之星程序设计大赛初赛题目 1 饭团的烦恼 “午餐饭团“是百度内部参与人数最多的民间组织。 同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。 参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。 但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。 饭团点菜的需求如下： 1 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。 2 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。 3 请紧记，百度饭团在各大餐馆享受 8 折优惠。 输入数据描述如下： 第一行包含三个整数 N ， M ， K （ 0N=16 ， 0M=N ， 0K=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。 紧接着 N 行，每行的格式如下： 菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否） 例： 水煮鱼 30 1 1 紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。 输出数据： 对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。 说明： 1 结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。 2 每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。 输入样例 3 2 2 水煮鱼 30 1 1 口水鸡 18 1 1 清炖豆腐 12 0 0 1 1 1 1 输出样例 口水鸡 清炖豆腐 12.00 时间要求： 1S 之内 Frogs NeighborhoodDescription未名湖附近共有n个大小湖泊L1, L2, ., Ln（其中包括未名湖），每个湖泊Li里住着一只青蛙Fi（1 = i = n）。如果湖泊Li和Lj之间有水路相连，则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ., xn，请你给出每两个湖泊之间的相连关系。Input第一行是测试数据的组数t（0 = t = 20）。每组数据包括两行，第一行是整数n（2 = n = 10），第二行是n个整数，x1, x2,., xn（0 = xi n）。Output对输入的每组测试数据，如果不存在可能的相连关系，输出NO。否则输出YES，并用n * n的矩阵表示湖泊间的相邻关系，即如果湖泊i与湖泊j之间有水路相连，则第i行的第j个数字为1，否则为0。每两个数字之间输出一个空格。如果存在多种可能，只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。输入样例 374 3 1 5 4 2 1 64 3 1 4 2 0 62 3 1 1 2 1 输出样例 Sample OutputYES0 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 NOYES0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 足球比赛吉林一中将举办一年一度的足球比赛。Andy的班级即将面临一组强队，就是去年的冠军队。Andy在比赛之前做了充分的准备，搜集了许多关于这支队伍的信息。在这支队伍中有N1个队员，通过过去比赛记录来看，他们总是在某些固定的队员之间传球。我们把对方的守门员编号为1号，我们的球门编号为N号，其他的为对方球员。资料里给出若干个整数对（ai，bi），表示球会从ai传到bi，如果ai1，代表球从对方守门员开出，如果biN，代表球攻入我方大门。其他情况均为对方队友间的传球配合。每组传球，还会给出一个实数pi，表示对方传球成功的概率，我方成功防守的概率就是1pi。我们会选择一些对方的传球路线做重点防御，使得不会出现某条从对方守门员到我方大门路径完全没有防守。假设我们选取的防御集合为S，我们定义了估价函数F（S）表示该种防守的可靠值。现在你需要计算这个可靠值最大值。输入输入包含多组测试数据。数据的第一行包含两个整数N，M (1= N = 100, 1= M = 400), 接下来M行，每行包含三个数字ai bi Pi (1 = ai, bi = N , 0 = Pi = 1 ).输入文件结束于 N = M = 0.输出 对于每组数据，如果最大值为0，输出“The opponent is too strong!” 如果最大值为1，输出“The opponent is too week!”，否则输出这个最大值，保留6位小数。样例输入4 41 2 0.52 4 0.62 3 0.53 4 0.84 41 2 1.02 3 1.03 4 1.02 4 1.04 41 2 02 3 1.03 4 1.02 4 1.00 0样例输出0.500000The opponent is too strong!The opponent is too week!提示对于第一组样例数据，我们可以选择第一条路线做重点防御，此时 F 为 ( (1-0.5) 1 ) = 0.5。如果我们选择第三条和第四条路线做重点防御，此时F为 ( (1-0.6) * (1-0.8) ) (1/2) = 0.282843。只选择第三条路线是不合法的，对方可以通过1，2，4将球轻松送入我方大门。 猪的安家Andy和Mary养了很多猪。他们想要给猪安家。但是Andy没有足够的猪圈，很多猪只能够在一个猪圈安家。举个例子，假如有16头猪，Andy建了3个猪圈，为了保证公平，剩下1头猪就没有地方安家了。Mary生气了，骂Andy没有脑子，并让他重新建立猪圈。这回Andy建造了5个猪圈，但是仍然有1头猪没有地方去，然后Andy又建造了7个猪圈，但是还有2头没有地方去。Andy都快疯了。你对这个事情感兴趣起来，你想通过Andy建造猪圈的过程，知道Andy家至少养了多少头猪。输入输入包含多组测试数据。每组数据第一行包含一个整数n (n = 10) Andy建立猪圈的次数，解下来n行，每行两个整数ai, bi( bi = ai = 1000), 表示Andy建立了ai个猪圈，有bi头猪没有去处。你可以假定(ai, aj) = 1.输出输出包含一个正整数，即为Andy家至少养猪的数目。样例输入33 15 17 2样例输出16Original: Andy Zhaus Contest No.1死亡迷宫背景很久以前，迷宫里住着一个恶魔。一天，我们伟大的英雄Andy无意中踏入了这个迷宫。不幸的是，他被困在这个迷宫当中了。恶魔在迷宫中召唤出了许多怪物，想要阻止Andy逃脱。在迷宫中，Andy遇到一个一位巫师。他给了Andy迷宫的地图，并告诉他迷宫的入口很快会关闭。Andy必须以非常快的速度到达入口，并且有足够的力气推开挡在入口的岩石。于是，Andy带着地图一路向着出口走去 问题给出Andy和各怪物的能量, 攻击力, 防御力，和迷宫的地图，请你计算一下 能量/耗时 的最大值。 当Andy走到有怪物的地方时，Andy会先进行攻击，然后怪物攻击，然后Andy当一方的能量小于等于0时攻击停止，并且小于等于0的一方死亡。攻击时，每次对方损耗的能量为己方的攻击力减去对方的防御力。 当Andy走到标有A,B,C的地方时，Andy的相应属性会得到增加。 对应关系如下：A 能量 + PB 攻击力 + QC 防御力 + R如果耗时超过100，那么门将永远也打不开了，我们的Andy也就永远的困在了这个暗无天日的迷宫之中 输入标准输入包含多组数据。每组数据的第一行有六个整数W (1 = W = 20), H (1 = H = 20), P (1 = P = 10), Q (1= Q = 10), R (1 = R = 10), M (0 = M = 5). 迷宫是由一个W*H的矩形区域构成。M表示怪物的数量。Andy每个单位时间可以移动到相邻的4个格中，当然，必须得保证目标格在矩形区域中。默认的起始时间是0。与怪物战斗不会花费额外的时间。其后H行每行严格包含W个字符。用如下的各字符表示这个迷宫的地图：#表示一堵墙（Andy是不会穿墙术的）. Marks an empty space, into which you can move.表示一块空地。S表示Andy的初始位置。E表示迷宫的入口。0表示各怪物。A表示属性增加地点。（使用次数仅限于一次）其后一行有三个整数，表示Andy的能量，攻击力，和防御力。其后M行，每行有四个整数，表示怪物的编号，和这个怪物的各属性。输出对于每组输入数据，输出 能量/耗时 的最大值，并保留4位小数。如果Andy不能到达出口，输出“impossible”。数据之间无空行。样例输入6 17 7 5 4 3#E.#.#A#.#.0.#.#B#1#2#.S.C#100 59 100 23 48 01 65 41 02 20 27 0样例输出3.7037平方数给出包含M个数字的列表，和列表中所有数字的所有质因数。求出最长的子列表，使得子列表中所有数字的乘积是一个完全平方数。 输入输入文件包含多组测试数据。第一行包含两个整数N , M ( 1 = N = 30 , 1 = M = 30000 ). N 是质因数的个数。接下来一行有N个整数，给出所有的质因数。然后一行包含M个整数，给出列表。 输入文件结束于N = M = 0. 输出对于每组数据，输出最长子列表的两个位置坐标l r。l是该子列表在列表中的起始位置，r是结束位置。如果多种情况都满足子列表长度最大，输出l最小的一个。如果不存在这样的子列表输出“None”。 样例输入3 42 3 54 9 25 63 42 3 56 6 3 30 0样例输出1 31 4Original: Andy Zhaus Contest No.1救援行动ProblemAngel被传说中神秘的邪恶的Moligpy人抓住了！他被关在一个迷宫中。迷宫的长、宽不超过200。 迷宫中有不可以越过的墙以及监狱的看守。 Angel的朋友带了一些救援队来到了迷宫中。他们的任务是：接近Angel。我们假设接近Angel就是到达Angel所在的位置。 假设移动需要1单位时间，杀死一个看守也需要1单位时间。到达一个格子以后，如果该格子有看守，则一定要杀死（否则会死 的很难看的只见那个看守开了9倍狙镜）。交给你的任务是，最少要多少单位时间，才能到达Angel所在的地方？ （只能向上、下、左、右4个方向移动） Input该题含有多组测试数据。 每组测试数据第一行二个整数n，m。表示迷宫的大小为n*m。 以后n行，每行m个时字符。其中“#”代表墙，“.”表示可以移动，“x”表示看守，“a”表示Angel，“r”表示救援队伍。 字母均为小写。 Output一行，代表救出Angel的最短时间。 如果救援小组永远不能达到Angel处，则输出“Poor ANGEL has to stay in the prison all his life.” Sample Input7 8#.#.#.a#.r.#.#x.#.#.#.#.#.Sample Output13埃及分数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(0ab1000),编程计算最好的表达方式。 Input第一行:N 表示有N组测试数据，每组测试数据为一行包含a,b(0ab1000)。 Output每组测试数据若干个数，自小到大排列，依次是单位分数的分母。 Sample Input119 45Sample Output5 6 18技能树Problem玩过Diablo的人对技能树一定是很熟悉的。一颗技能树的每个结点都是一项技能，要学会这项技能则需要耗费一定的技能点数。 只有学会了某一项技能以后，才能继续学习它的后继技能。每项技能又有着不同的级别，级别越高效果越好，而技能的升级也是 需要耗费技能点数的。 有个玩家积攒了一定的技能点数，他想尽可能地利用这些技能点数来达到最好的效果。因此他给所有的级别都打上了分，他认为 效果越好的分数也越高。现在他要你帮忙寻找一个分配技能点数的方案，使得分数总和最高。 Input该题有多组测试数据。 每组测试数据第一行是一个整数n（1=n=20）,表示所有不同技能的总数。 接下来依次给出n个不同技能的详细情况。 每个技能描述包括5行。 第一行是该技能的名称。 第2行是该技能在技能树中父技能的名称，名称为None则表示该技能不需要任何的先修技能便能学习。 第3行是一个整数L（1=L=20），表示这项技能所能拥有的最高级别。 第4行共有L个整数，其中第I个整数表示从地I-1级升到第I级所需要的技能点数（0级表示没有学习过）。 第5行包括L个整数，其中第I个整数表示从第I-1级升级到第I级的效果评分，分数不超过20。 在技能描述之后，共有两行，第1行是一个整数P，表示目前所拥有的技能点数。 接下来1行是N个整数，依次表示角色当前习得的技能级别，0表示还未学习。这里不会出现非法情况。 Output每组测试数据只需输出最佳分配方案所得的分数总和。 Sample Input3Freezing ArrowIce Arrow3 3 3 3 15 4 6Ice ArrowCold Arrow24 310 17Cold ArrowNone33 3 215 5 2100 0 1Sample Output42邮递员的烦恼Problem邮递员每天的任务是把邮件送到各家各户.日子长了,邮递员就会想,我每天是不是跑了很多的冤枉路呢?能不能找到一条最短的路 让我尽快的完成任务.这个问题困扰了他很久很久.最后他决定找一个程序员来解决这个问题. 邮递员所在的城市共有m调东西向的马路和n调南北向的马路.这m+n条马路把整个城市分成了(m-1)*(n-1)个街区.每个街区长 150米,宽120米.每一段马路上隔10米有一个门牌号.门牌号从1开始,由东向西,由北向南一次增加.所有奇数门牌号一律位于北侧 或者东侧，偶数的门牌一律位于南侧或者西侧。因此每一段东西向马路上共有28个门牌号码，每一段南北向的马路上共有22个门 牌号码。但是在环城的马路上是没有奇数号码或是偶数号码的门牌。 见下图: 每条马路都有一个编号，用H表示东西向，V表示南北方向，后面跟一个数表示由东向西数或者由北向南数第几条马路。譬如H1表 示最北边的东西向的马路，V2表示由东向西第二条南北向的马路。一个地址可以用马路编号+门牌号表示。邮递员每天要送信 到许多不同的地址。由于他骑的是自行车，因此可以在马路上做U字形转弯。 现在告诉你所有要送达的地址以及邮局的所有地址，请你为他规划一条最短的路线，使得他可以从邮局出发，把所有的邮件送出 去以后再回到邮局，马路的宽度忽略不计。 Input该题含有多组测试数据。 每组测试数据第一行是三个整数m,n,L(2=m,n=10,0=L=17)依次表示城市中东西向,南北向马路条数和邮递员要送达的不同地址数。 接下来L行每行是一个地址，马路编号和门牌号之间用一个空格分隔。 最后一行是邮局的地址。 所有地址都保证是合法的且没有任何两个相同。 Output输出的格式说明 Sample Input5 5 3V3 32V5 41H5 51H2 61Sample Output1380砝码问题Problem有一组砝码，重量互不相等，分别为m1、m2、m3mn；它们可取的最大数量分别为x1、x2、x3xn。 现要用这些砝码去称物体的重量,问能称出多少种不同的重量。 Input第一行为一整数t,表示有t组测试数据。 每组测试数据第一行一个整数n（n=10），表示有多种不同的砝码； 第二行n个整数（中间用空格分隔），m1、m2、m3mn，分别表示n个砝码的重量；（1=mi=20） 第三行n个整数（中间用空格分隔），x1、x2、x3xn，分别表示n个砝码可取的最大数量。（1=xi=20） Output每组数据输出仅一行，一个整数，表示利用给定的砝码可以称出的不同的重量数。 注：包括0。 Sample Input121 22 1Sample Output5嗅探器Problem某军搞信息对抗实战演习.红军成功地侵入了蓝军的内部网络.蓝军共有两个信息中心.红军计划在某台中间服务器上安装一个嗅探 器,从而能够侦听到两个信息中心互相交换的所有信息.但是蓝军的网络相当的庞大,数据包从一个信息中心传到另一个信息中心可 以不止有一条通路.现在需要你尽快地解决这个问题.应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获? Input该题含有多组测试数据。 第一行一个整数n(1=n=100),表示蓝军网络中服务器的数目. 接下来若干行是对蓝军网络的拓扑结构描述. 每行是两个整数i,j表示编号为I和编号为j的两台服务器间存在连接(显然连接是双向的).服务器的编号从1开始.描述一两个0结束. 再接下来一行是两个整数a,b分别表示两个中心服务器的编号. Output输出编号。如果有多个解输出编号最小的一个.如果找不到任何解,输出”No solution”. Sample Input52 12 51 45 32 35 10 0采药【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件medic.in的第一行有两个整数T（1 = T = 1000）和M（1 = M = 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。【样例输入】70 371 10069 11 2【样例输出】3【数据规模】对于30%的数据，M = 10；对于全部的数据，M = 100。4 2Sample Output1校门外的树【问题描述】某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。【输入文件】输入文件tree.in的第一行有两个整数L（1 = L = 10000）和 M（1 = M = 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。【输出文件】输出文件tree.out包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。【样例输入】500 3150 300100 200470 471【样例输出】298【数据规模】对于20%的数据，区域之间没有重合的部分；对于其它