首届全国中医药院校大学生程序设计竞赛试题.doc

Problem A: 序列的混乱程度Time limit:1sMemory limit:128MBDescription有一个长度为n的正整数序列，一个序列的混乱程度定义为这个序列的最大值和最小值之差。请编写一个程序，计算一个序列的混乱程度。Input输入的第一行为一个正整数T（T=1000），表示一共有T组测试数据。每组测试数据的第一行为一个正整数n（1=n=1000），代表这个序列的长度。第二行为n个正整数，代表这个序列。序列中元素的大小不会超过1000。Output对于每个测试数据，输出一行包含一个正整数，代表对应序列的混乱程度。Sample Input251 2 3 4 551 9 2 4 8Sample Output48Problem B: 随机数Time limit:1sMemory limit:128MBDescription有一个rand(n)的函数，它的作用是产生一个在0,n）的随机整数。现在有另外一个函数，它的代码如下：int random(int n,int m)return rand(n)+m;显而易见的是函数random(n,m)可以产生任意范围的随机数。现在问题来了，如果我想要产生范围在a,b)内的一个随机数，那么对应的n,m分别为多少？Input输入的第一行为一个正整数T（T=1000），表示一共有T组测试数据。对于每组测试数据包含两个整数a,b(a=b)。Output对于每组测试数据，输出一行包含两个整数n和m，两个整数中间有一个空格分隔。Sample Input20 51 4Sample Output5 03 1Problem C: 完美序列Time limit:1sMemory limit:128MBDescription已知一个长度为l的序列：b1,b2,b3,bl（1=b1=b2=b3=bl=n）。若这个序列满足每个元素是它后续元素的因子，换句话说就是对于任意的i（2=i=l）都满足bi%bi-1=0（其中“%”代表求余），则称这个序列是完美的。你的任务是对于给定的n和l，计算出一共有多少序列是完美序列。由于答案很大，所有输出答案对1000000007取余后的结果。Input输入的第一行为一个正整数T（T=1000），表示一共有T组测试数据。对于每组测试数据包含两个整数n,l（1=n,l=2000），分别代表序列中元素大小的最大值和序列的长度。Output对于每组测试数据，输出一行包含一个整数，代表答案对1000000007取余后的结果。Sample Input33 26 42 1Sample Output5392Problem D: 第k大数Time limit:10sMemory limit:128MBDescription有两个序列a,b，他们的长度分别为n和m，那么将两个序列中的元素对应相乘后得到的n*m个元素从大到小排列后的第k个元素是什么？Input输入的第一行为一个正整数T（T=10），表示一共有T组测试数据。每组测试数据的第一行有三个正整数n,m和k（1=n,m=100000,1=k=n*m），分别代表a序列的长度、b序列的长度以及所求元素的下标。第二行为n个正整数代表序列a。第三行为m个正整数代表序列b。序列中所有元素的大小满足1,10000。Output对于每组测试数据，输出一行包含一个整数代表第k大的元素是多少。Sample Input33 2 31 2 31 22 2 11 11 12 2 41 11 1Sample Output311Problem E: 选房子Time limit:1sMemory limit:128MBDescription栋栋和李剑已经大四了，想要出去找房子住。他们一共看中了n套房子。其中第i套房子已经住了ai个人了，它最多能住bi个人。栋栋和李剑想要住在一起，那么请问他们有几套可以选择的房子？Input输入的第一行为一个正整数T（T=10），表示一共有T组测试数据。每组测试数据的第一行有一个正整数n（1=n=100），代表一共有n套房子。接下来n行，每行有两个正整数ai,bi（1=ai=bi=100），分别代表现在已经住了ai个人和最多能住bi个人。Output对于每组测试数据，输出一行包含一个整数，代表他们可以选择的房子的数量。Sample Input221 21 331 102 103 10Sample Output13Problem F: GameTime limit:1sMemory limit:128MBDescriptionDongDong is playing a tower defense game. In this game, we have two kinds of resource: money and wood. At the beginning of the game, DongDong possesses G money and no wood. Before the first round DongDong can use this money, and he can get money only by defeating the monsters. There is only one monster in each round, and DongDong can get money when the monster is dead. Meanwhile, DongDong can use this money in the current round. DongDong will lose the game when his hardiness is lower than the monsters attacking value, otherwise he will kill the monster. The money can increase the hardiness that one unit money can increase one unit hardiness. In addition, DongDongs initial hardiness is 0. Furthermore, the money can also increase the efficiency of lumbering. The efficiency of lumbering means the number of wood that every worker can collect at each round. The initial efficiency of lumbering is W. If DongDong trains a worker in the current round, then the worker will start working in the following rounds. DongDong will pay F money to increase one unit efficiency of lumbering or train one worker. Also, DongDong have no workers in the initial time. Only workers can lumber. Because the wood is very precious, DongDong wants to know how much wood he can get at most after N rounds?InputThe first line contains a positive integer T(T=1000), which means T test cases.The first line of each test case contains 4 positive integers N, F, W,G(1=N=1000, 1=F,W=10000, 1=G=1000000), which means N rounds, the cost of training a worker or increasing one unit efficiency of lumbering F, the initial efficiency of lumbering W, the initial money G, respectively. Then following N lines, each line contains two positive integers Ai, Gi, Ai means the attacking value of monsters, Gi means the money that Dong Dong can get after he kills the monster.OutputFor each case, if DongDong cannot finish N round game, please output “Its useless to collect wood.” (without quotes), otherwise print the most units of wood that DongDong can get.Sample Input35 1 1 11 11 11 11 11 14 10 7 1001 12 23 3100000 43 10 7 1010 1010 1020 10Sample Output13Its useless to collect wood.14Problem G: NumbersTime limit:1sMemory limit:128MBDescriptionDongDong is fond of numbers, and he has a positive integer P. Meanwhile, there is a rule that is: A positive integer D that satisfies the following rules:1. D is one of the factors of P.2. D and P have a same bit at least under the binary system.So DongDong wants to know how many positive integers D there are.InputThe first line contains a positive integer T(T=1000), which means T test cases.Then comes T lines, each line contains a positive integer P(1=p=1000000000).OutputFor each case, print the number of positive integers D that satisfies the rules.Sample Input2110Sample Output12Problem H: Counting WordsTime limit:1sMemory limit:128MBDescriptionDongDong prefers English words to English sentences, so he wants to count the words of a sentence. Could you help him?InputThe first line contains a positive integer T(T=1000), which means T test cases.Then comes T lines, each line contains a string which combines with s