竞赛：Round 1
说明：对于每个试题，输入输出均为标准的屏幕（控制台）输入输出设备。时间限制为1秒，内存理论不限，但由于环境限制，最多为500Mb。
问题A
描述
在数据库中检索一个数据是很重要的操作。现给出N个升序正整数，并给出一个要查找的数A，如果在N个数的序列中那么输出这个数，如果找不到则输出-1。
输入
本题有多组测试数据。第一行为测试数据的个数。每组数据
第一行为一个整数n(n <= 100000)。
第二行为n个升序整数。
第三行为要查找的数的个数m(m<=10000)
第四行为m个数，表示要查找的数
输出
对于每一组数据输出m行，若找到则输出目标数，否则输出-1
输入样例
1
5
1 2 3 4 5
3
2 6 4
输出样例
2
-1
4
问题B
问题描述
数的扩展是一个比较经典的问题。
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n然后对此自然数按照如下方法进行处理:
1. 不作任何处理;
2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
输入
本题有多组测试数据。第一行为测试数据的个数。每组数据
有一个整数n(n <= 1000)。
输出
对于每组数据输出一行，输出一个整数，即方案（扩充）种数。
输入样例
2
6
10
输出样例
6
14
注：满足条件的数为 6 (此部分不必输出)
16
26
126
36
136
问题C
问题描述
在一个果园里，PF已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。PF决定把所有的果子合成一堆。
每一次合并，PF可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。PF在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以PF在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使PF耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入
本题有多组测试数据。第一行为测试数据的个数。每组数据
包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。
输出
对于每组数据输出一行，一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2^31。
输入样例
1
3
1 2 9
输出样例
15
问题D
描述
在《SDU to 贤文庄之大逃亡》电影中，PengFei等人一起逃亡，现在有许多的东西要放到PF的包里面，以便通宵时肚子饿的时候有东西吃，但是包的大小有限，所以我们只能够在里面放入非常重要的物品，现在给出该种物品的数量、体积、价值的数值，希望你能够算出怎样能使背包的价值最大的组合方式，并且输出这个数值，PF会非常地感谢你。
输入
本题有多组测试数据。第一行为测试数据的个数。每组数据
第一行有2个整数，物品种数n和背包装载体积v。
2行到n+1行每行3个整数，为第i种物品的数量m、体积w、价值s。
（数据规模：1<=v<=500，1<=n<=2000，1<=m<=5000，1<=w<=20，1<=s<=100）
输出
对于每组数据输出一行，仅包含一个整数，即为能拿到的最大的物品价值总和。
输入样例
1
2 10
3 4 3
2 2 5
输出样例
13
注：选第一种一个，第二种两个。结果为3*1+5*2=13
问题E
描述
山东大学领导们觉得齐鲁软件学院校区的MM太少，不和谐，于是乎便想把外国语学院也搬迁到齐鲁软件学院校区。但是可怜的小校区只有四个宿舍楼（况且有三个楼住男生），所以为了让外国语学院的MM有漂亮的宿舍楼，学校决定加盖楼房。为了把新宿舍楼盖的漂亮一点，学校决定通过一个考验智商的游戏来选拔优秀的楼房设计师。
PF想了想，觉得不错就报名了，但由于问题复杂，他需要聪明的你为他设计一个程序，来解决这个游戏。
游戏的规则如下：
现有一游戏，玩它时将会有方块有顺序的从屏幕顶端掉下至底部，当它碰到障碍物或底部时将停下，同时自己变成障碍物。游戏规则规定，只能从方块下落前决定下落时的横向位置，使这个方块变成障碍物后的高度最低，且如果有几种横向位置使这个方块变成障碍物后的高度最低时，取最左边的横向位置下落。
输入
本题有多组测试数据。第一行为测试数据的个数。每组数据
（1）第一行有2个整数，方块数n(1<=n<=100)和屏幕宽度w(1<=w<=20)。
（2）2行到n+1行每行1个整数，为第i个方块的边长a(1<=a<=w)。
输出
对于每组数据输出一行，仅包含一个整数，即为所有障碍物的最高点高度。
输入样例
1
3 5
2
1
3
输出样例
4
注：
绿的为方块1，蓝的为方块2，紫的为方块3。
//每次都选择保证最底点且最左
问题F
描述
PF同学最近养了一些淘气的兔子，但是由于兔子们老是不在自己的位置带着，所以他比较头痛，于是他就把这些兔子分在几个笼子里装着，每个笼子有X个位置可以装兔子，并把这些位置标号为1、2、3……X，然后又把每一个兔子标号为1、2、3……X。但是这些兔子调皮，所以有可能跑到别的位置，而别的位置的兔子就再找别的位置安顿下。在某一时刻，PF发现在位的兔子一共有A个，在另一时刻在位的兔子有B个。
现给出N个笼子的容量和每个笼子的容量，求出在兔子的期望个数。
输入
本题有多组测试数据。第一行为测试数据的个数。每组数据
第一行为一个数N(1<=N<=100)，表示笼子的个数。
第二行为N个数Ai(0<=Ai<=1000)，表示第i个笼子的容量。
输出
对于每组数据输出一行，输出一个数，表示正好在位兔子个数的期望，结果四舍五入。
输入样例
1
3
1 1 2
输出样例
3