1、安徽省2012年“达内杯”大学生程序设计竞赛目录Problem A Alice的车牌号Problem B Bella的冒险之旅Problem C Catherine的魔法符文Problem D Diana的组队烦恼Problem E 比特等级Problem F 寻找砝码集Problem G 奇怪的电梯Problem H 宝盒密码Problem I 法默尔的农场Problem J 银河系5A风景区2012.5Problem A Alice的车牌号DescriptionAlice是NFS的死忠。一天，Alice想给自己游戏中的兰博基尼换个新车牌。NFS会随机生成一个由小写英文字母与数字组成的6位的
2、车牌号给Alice，但是Alice是个很迷信的人，如果车牌中包含13这个数字，她就会放弃这个车牌号，否者她会接受这个新的车牌号，那么现在请写个程序以判断Alice是否会接受游戏生成给她的新车牌。Input输入数据第一行有一个整数T，表示用T组测试数据。对于每组测试数据，每行都会有一个长度为6的字符串，表示生成的车牌号。保证字符串仅由数字和小写英文字母组成。Output对于每组测试数据，输出占一行，首先应当输出一行”Case #k: ”，k表示第k组测试数据，然后对于每组测试数据，如果Alice接受这个车牌，输出”Yes, I like it!”，否则，输出”No, its terrible!”
3、。Sample Input2icpc12zzzz13Sample OutputCase #1: Yes, I like it!Case #2: No, its terrible!Problem B Bella的冒险之旅Diablo III终于开始发售了，Bella已经等了整整10年了！在Diablo III中有一个叫做Multiple Travel的任务，在一个超空间领域，有n（0 n 10）座悬空孤岛，每座孤岛的标号从0到n-1，每座孤岛上都拥有至少一个传送门，每一扇传送门都会将玩家从所在孤岛传送至另一座指定孤岛上的传送门，即一对传送门会连接一对悬空孤岛。同时，传送门只有n-1对，但是保证所
4、有的孤岛相互之间都是可以直接或者间接到达的。玩家必须选择某座孤岛为起点，在此后的任何时候，只要玩家愿意，都可以结束这个任务，接着玩家可以利用传送门去到达其他的孤岛，最后结束任务之后，NPC会根据玩家的旅行线路给出不同的纪念道具。需要注意的是，每个玩家都可以无限次的接这个任务，但是每次走的旅行线路如果与之前某次接这个任务时走的旅行线路“雷同”，那么NPC就不会给玩家纪念道具-_-|，而所谓的“雷同”是指：两次旅行，所使用的传送门及到达的孤岛可以通过某种映射关系，相互转化，那么就被认为是“雷同”的。（详细情况可以看Hint）现在Bella想知道自己最多可以拿到多少种不同的纪念道具。对于每组测试数据
5、，每行都会有一个正整数n（n 10），n如上所述。接着会有n-1行数据，每行都有两个正整数a,b，表示两座标号为a,b的孤岛之间有传送门相连。 ”，k表示第k组测试数据，接着按题目要求输出Bella最多可以拿到的不同的纪念道具的数量。50 11 21 33 494 65 70 56 30 23 28 3 6 21Hint对于第一组测试数据不同的旅行线路如下：Problem C Catherine的魔法符文Catherine在伊苏的一个彩蛋关卡中碰到了麻烦，为了通过NPC的考验，Catherine必须用数字按NPC的要求摆出一个菱形的魔法符文图案，NPC会给出一个正整数n（n 10），这个菱形的
6、魔法符文图案由数字组成，菱形的中心是数字n，周围同样由数字包围，距离菱形中心越远，包围的数字逐步递减，直到递减为1。这个问题显然难倒了刚入手伊苏这个经典RPG的Catherine，那现在就请各位帮帮Catherine吧对于每组测试数据，首先在第一行应当输出一行”Case #k: ”，k表示第k组测试数据，从第二行开始输出NPC要求的魔法符文。每组测试数据之后应该输出一个换行。3 11 2 11Case # 2: 1 2 11 2 3 2 1输出的每行魔法符文后都没有多余的空格，同时不要遗漏必要的空格。Problem D Diana的组队烦恼Diana是一个悲惨的被WoW吞噬了几乎全部生命的玩家
7、，在一次跟朋友组队打副本的时候，Diana碰到了麻烦，Diana的团队总共有n（0 20）个人，副本中的一个迷宫里有k（0 k 20）扇一样的大门，每扇门背后都有一个同样的BOSS，现在Diana的团队必须同时进入这k扇大门里去打败其中的BOSS，Diana想知道她的团队可以有几种分组方式，使得保证每扇门中至少有一名自己的队友，同时，由于每个WoWer都是不同的，只有完全不同人员的分组的方案才能被认为是不同的。对于每组测试数据，第一行会有两个正整数n,k（0 n, k 20），n, k如上所述。然后输出最多可能的分组个数。所有数据保证在64位整数之内。2 14 2 7对于第二组测试数据，所有可
8、能的情况应该是这样的1. A, B, C, D2. B, A, C, D3. C, A, B, D4. D, A, B, C5. A, B, C, D6. A, C, B, D7. A, D, B, CProblem E 比特等级犹如古希腊传说中的亚特兰蒂斯一样，数码世界中也存在一个神奇的王国-比特国，比特国是一个等级森严的国度，而标识比特国中每个人等级的标志就是每个人与生俱来的一个比特号n（0 231-1），而每个人的等级值是指他的比特号在二进制下最低的非0比特位的值，例如一个人的比特号是28，转化为二进制就是11100，那么最低的非0比特位就是4，那么他的等级值就是4。现在你需要设计一个程
9、序去计算比特国中每个人的等级值。首先是一个整数 t，表示有 t 组测试数据。（t = 1000）对于每组测试数据，每行都会有一个32bit正整数n，n如上所述。然后应该输出对应的结果。2888 4 8Problem F 寻找砝码集现有重量为w1, w2, w3,.,wn的n种物品，你需要找到一组物品集合作为砝码集，使得这n种物品每件都能被这个砝码集在天平上称量，并且使这个砝码集中含有的物品种类数量最小。物品w能被砝码集y称量的意思是指：把物品w放在天平的左边，然后从砝码集y中选取一些物品，每件物品任意放在天平左边或者右边，最终使得天平平衡。这个过程中你可以使用组成砝码集y的每种物品任意多次。有
10、多组测试数据。每组数据有两行，第一行是一个整数n（1 = n = 50），第二行包含n个整数w1,w2,.,wn（ 1 = wi = 10000000 ），表示这n种物品的重量，输入以一个0结束。输出一个正整数，代表这个砝码集中含有的物品种类数量。45 4 1 82 3 8 913 5 11Problem G奇怪的电梯有一个奇怪的电梯，一共N层，每一层都有一个对应的数字Ki（1 = Ki = N）。电梯在第i 层停靠时不能选择去哪一层，只能按向上或者向下按钮，然后电梯就会相应的往上或者往下运行到i+Ki层或者i-Ki层，并且电梯不能运行到超过N层或者低于1层。现在问题是：你在A层，想去B层，你
11、必须按向上或者向下按钮至少多少次才能如愿？每组测试数据有两行。第一行包含3个整数N，A，B（1 = N ,A,B = 200）。第二行有N个整数，分别是K1，K2，.Kn。输入以一个单独的0结束。输出从A层到B层必须至少按下按钮的次数。如果从A层不能到达B层，输出-1。5 1 53 3 1 2 5Problem H 宝盒密码勇敢的 Sbarrow 船长驾着白珍珠号，环游大半个地球，历经艰险，终于找到了琼斯的宝盒。可惜宝盒异常坚固，怎么都打不开，上面只有四个每隔一分钟变化一次的整数，还有一个用来输入密码的锁。Sbarrow 尝试了很多密码，但都不对。不过一天夜里，他得到了启迪，卡里布索女神托梦给
12、他，告诉他：盒子的密码是不断变化的，如果设某一时间盒子上的四个整数，从左到右分别为l,h,a,b则此时盒子的密码为满足以下三个条件的最小的整数 x：1. l = x 且 x = h2. a mod x = 03. x mod b = 0Sbarrow 虽然勇敢，也很聪明，但他可不是一个优秀的算法专家，现在请你来帮他解决这个问题吧。每组有四个整数 l, h, a, b （ 1 = l, h, a, b = 109 ）。对于每组数据输出一行 Case #c: x，c 表示第几组测试数据（从1开始），x 为结果，若不存在满足这些条件的整数，则结果为 -1。5 10 18 319 21 18 3 6
13、-1Problem I 法默尔的农场法默尔有一个农场，农场由很多高低不同的小山丘组成。每到雨季，根据水位的不同，农场中会出现不同数目的“小岛”（当水位大于等于某座山丘的高度时，该山丘就会被淹没）。你要做的是根据给定的水位，计算有多少“小岛”。农场是一维的，如下图：当水位为4时，有四个“小岛”；当水位为5时，有三个“小岛”。只有一组测试数据。= 20000 ），表示有多少山丘。第二行是n个整数，从左到右，表示每座山丘的高度，每两个数之间用一个空格隔开，（山丘高度大于等于1，小于等于108 ）。第三行是一个整数 q （ 1 = q = 20000 ），表示有多少询问。接下来q行，每行一个整数，表示
14、水位，（大于等于1，小于等于108）。对于每个给定的水位，输出一个整数，占一行，表示有多少“小岛”。106 2 9 8 10 1 5 3 9 7Problem J 银河系5A风景区巴尔坦星是个银河系中一个著名的观光景点，它之所有著名，是因为巴尔坦星有四颗卫星，而且四颗卫星距离巴尔坦星的距离都是一样的！某天，巴尔坦星上的居民们想知道自己星球所处的具体三维宇宙坐标，因为科技落后，巴尔坦星上的居民只有某个时刻测得的四颗卫星的坐标。现在请你写个程序帮可怜的巴尔坦星居民给自己的星球定下位吧。第一行是一个整数 t ，表示有 t 组测试数据。= 30）每组数据占四行，表示四颗卫星的坐标。每行三个实数 x, y, z 表示该点的坐标为 （x,y,z）。输入数据保证每组的数据都可以确定巴尔坦星，设巴尔坦星的坐标为（ox, oy, oz），每颗卫星到巴尔坦星的距离都是r则以下不等式总是成立：-500 = ox, oy, oz = 500， 500 = r = 1000。对于每组数据输出一行；Case #k: x y z 。k表示第k组数据，x, y, z 表示巴尔坦星的坐标（均保留到小数点后一位）。1.1 0 00.1 1.0 00.1 -1.0 00.1 0 1.0 0.1 0.0 0.0
