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