ACM测试题.doc

Turn the corner

Mr. West bought a new car! So he is travelling around the city.
  One day he comes to a vertical corner. The street he is currently in has a width x, the street he wants to turn to has a width y. The car has a length l and a width d.
  Can Mr. West go across the corner?
Input
  Every line has four real numbers, x, y, l and w.
  Proceed to the end of file.
Output
  If he can go across the corner, print "yes". Print "no" otherwise.
Sample Input
10 6 13.5 4
10 6 14.5 4
Sample Output
yes
no

100!
In these days you can more and more often happen to see programs which perform some useful calculations being executed rather then trivial screen savers. Some of them check the system message queue and in case of finding it empty (for examples somebody is editing a file and stays idle for some time) execute its own algorithm.
As an examples we can give programs which calculate primary numbers.

One can also imagine a program which calculates a factorial of given numbers. In this case it is the time complexity of order O(n) which makes troubles, but the memory requirements. Considering the fact that 500! gives 1135-digit number no standard, neither integer nor floating, data type is applicable here.

Your task is to write a programs which calculates a factorial of a given number.
Assumptions: Value of a number "n" which factorial should be calculated of does not exceed 100.
Input

Input the integer N(N<=100)
Output

output contain calculated value n!.

Mind that visually big numbers will be automatically broken after 80 characters.
Sample Input
10
30
50
100

Sample Output
10!
3628800

30!
265252859812191058636308480000000

50!
30414093201713378043612608166064768844377641568960512000000000000

100!
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

最佳调度
假设有N个任务由K个可并行工作的机器来完成。完成任务I需要时间为Ti。请设计一个算法找出完成这N个任务的最佳调度，使得完成全部任务的时间最早。
输入:
第一行有两个正整数N和K，第二行输入N个正整数代表完成N个任务需要的时间。
输出：
完成全部任务的最短时间
Sample Input
7 3
2 14 4 16 6 5 3
Sample Output
17

Team Queue
Queues and Priority（优先）Queues are data structures which are known to most computer scientists. The Team Queue, however, is not so well known, though it occurs often in everyday life. At lunch time the queue in front of the Mensa（饭店名）is a team queue, for example.
In a team queue each element belongs to a team. If an element enters the queue, it first searches the queue from head to tail to check if some of its teammates (elements of the same team) are already in the queue. If yes, it enters the queue right behind them. If not, it enters the queue at the tail and becomes the new last element (bad luck). Dequeuing（出队）is done like in normal queues: elements are processed from head to tail in the order they appear in the team queue.
Your task is to write a program that simulates such a team queue.
Input
The input will contain one test cases. test case begins with the number of teams t (1<=t<=1000). Then t team descriptions follow, each one consisting of the number of elements belonging to the team and the elements themselves. Elements are integers in the range 0 - 999999. A team may consist of up to 1000 elements.
Finally, a list of commands follows. There are three different kinds of commands:
Ø ENQUEUE x - enter element x into the team queue
Ø DEQUEUE - process the first element and remove it from the queue
Ø STOP - end of test case
The input will be terminated by a value of 0 for t.
Output
For each DEQUEUE command, print the element which is dequeued on a single line. Print a blank line after each test case, even after the last one.

Sample Output
101
102
103
201
202
203

Sample Input
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0