【试题五】
从5月12日下午地震发生至今已经超过48小时，根据地震救灾的常识推算，未来24小时将是救灾最后的黄金时间。时间在无情的流逝，数以万计的灾民依旧命悬喘息之间。现在，数万军民正日夜奋战在抢救灾民第一线。从人员的组织协调到救灾物资的后援运输，每一个环节都直接关系到救灾的效果好坏。
由于通往各灾区的道路完全中断，大批救援物资只好空投到各个灾区。某军区准备了一批物资, 恰好能均分到处于环形的N个灾区中。遗憾的是，由于余震不断，天气恶劣等原因，落到各灾区的数量不相同。
正如温家宝总理所一再强调的“抢救人的生命，是这次救灾工作的重中之重” 。为了保证救灾的效率不会平白消耗， 当地的民间救助组织可以选择将落到自己所在区的物资传送到左边或者右边相邻的灾区。为了公平起见，我们希望通过相邻灾区的相互传送，最终使所有的灾区获得相同数量的物资。假设一个物资从一个灾区传送到另一个灾区付出的代价是1, 问怎样进行传送，使得所付出的总代价最小。 【标准输入】
第一行： N 表示处于环形的灾区数
接下来n行： 每行一个整数Ai, 表示第i个灾区得到的物质数量。 【标准输出】
输出只有一个数, 表示传送物资付出的最小总代价
【约束条件】 （1） N<=1000000
（2） Ai>=0, 保证Ai在长整型范围内, Ai的总和在int64/long long范围内. （3）时间限制： 1000MS 【 样 例 】
标准输入 4 1 2 5 4
标准输出 4 【试题六】 Time Limit: 1000MS
The disaster is order, and the time is life. Relief troops must reach the disaster scene as fast as possible. At 10:00 on the 13th, in the disaster relief headquarters of the Chengdu Military Area, Li Shiming, commander of the Chengdu Military Area Command, shouted loudly :\matter generals or soldiers, whoever reach the quake-hit areas in the earliest time will be awarded the glory.\
We may assume that all the soldiers except \run from Chengdu to Wenchuan at a fixed speed. Yongshi is a soldier with a different running habit – he always tries to follow another soldier to avoid running alone. When Yongshi gets to Chengdu , he will look for someone who is setting off to Wenchuan. If he finds someone, he will follow that soldier, or if not, he will wait for someone to follow. On the way from Chengdu to Wencuan, at any time if a faster soldier surpassed Yongshi , he will leave the soldier he is following and speed up to follow the faster one.
We assume the distance from Chengdu to Wenchuan is 95 kilometers and the time that Yongshi gets to Chengdu is zero. Given the set off time and speed of the other soldier, your task is to give the time when Yongshi arrives at Wenchuan.
【Input】
There are several test cases (<=10 test cases). The first line of each case is N (1 <= N <= 1000) representing the number of soldier (excluding Yongshi ). N = 0 ends the input. The following N lines are information of N different soldiers, in such format: Vi Ti
Vi is a positive integer <= 30, indicating the speed of the i-th soldier (kph, kilometers per hour). Ti is the set off time of the i-th soldier, which is an integer and counted in minutes. In any case it is assured that there always exists a nonnegative Ti. -1000<= Ti <=1000
【Output 】
Output one line for each case: the arrival time of Yongshi. Round up the value when dealing with a fraction.
Sample Input Sample Output
4 214 10 0 271 12 -15 15 19 30 24 2 21 0 22 34 0
【试题七】
George took sticks of the same length and cut them randomly until all parts became at most 20 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
【Input】
Input consists of multiple problem instances. Each instance contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
【Output】
The output should contains the smallest possible length of original sticks, one per line.
Sample Input
9
5 2 1 5 2 1 5 2 1 4
1 2 3 4 0
Sample Output
6 5
Time Limit: 1000MS
【试题八】
An 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.
【Input】
Input 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. 1 <= m <= 100. 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.
【Output】
For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined: y y y? y. Sorted sequence cannot be determined. Inconsistency found.
y y y… y is the sorted, ascending sequence.
Sample Input Sample Output
4 6 Sorted sequence determined: A B C D. A
A
考试时间： 5小时（9：00 ~ 14：00） 文件命名： 提交源程序名为：T题号。如第二题应提交：T2.c 时间限制: 每题运行时间不超过1000MS
【试题一】
Dr.Kong的机器人
Dr.Kong设计了一个可以前进或后退机器人，该机器人在每个位置i会得到一个移动步数的指令Ki (i=1,2?N),聪明的机器人自己会判断是要前进Ki步还是后退Ki步。
例如：给定指令序列(3 3 1 2 5)，表示机器人在第1个位置时，可以前进3步到第4个位置，此时后退是不起作用的，出界；机器人在第2个位置时，可以前进3步到第5个位置，此时后退是不起作用的，出界；机器人在第3个位置时，可以前进1步到第4个位置，也可以后退1步到第2个位置等等。
你认为，对给定的两个位置A,B, 聪明的机器人从A位置走到B位置至少要判断几次？ 【标准输入】
第一行: M 表示以下有M组测试数据（0 头一行：N A B ( 1≤ N≤ 50, 1≤A,B ≤N ) 下一行: K1 K2?..Kn ( 0<=Ki<=N ) 【标准输出】 输出有M行，第i行为第i组测试数据的最少判断次数, 若无法到达，则输出-1。 【 样 例 】 标准输入 2 5 1 5 3 3 1 2 5 8 5 3 1 2 1 5 3 1 1 1 标准输出 3 -1 【试题二】 奇特的艺术品 Dr.Kong设计了一件艺术品，该艺术品由N个构件堆叠而成，N个构件从高到低按层编号依次为1，2，??,N。艺术品展出后，引起了强烈的反映。Dr.Kong观察到，人们尤其对作品的高端部分评价甚多。 狂热的Dr.Kong一激动，对组成该艺术品的N个构件重新组合，比如：把第6层到第12层的构件搬下来，想一想，然后整体放到剩下构件的第7层下面；过一会儿，又把第2层到第9层的构件搬下来，整体放到剩下构件的第1层下面等等。于是，Dr.Kong在进行了连续若干次“搬来搬去”后，还是这N个构件，又诞生了一件新的艺术品。 编程：请输出新的艺术品最高十层构件的编号。 【标准输入】 第一行: N K 表示构件的总数和“搬来搬去”的总次数 第2~K+1行：A B C 表示要搬动的构件（即从第A层到第B层）整个放在第C层下面； 如果C等于0，则要搬动的构件将放到最高层。 【标准输出】 由十行组成，分别为组成新艺术品的第一层到第十层构件的编号。 【约束条件】