第三届仲恺农业工程学院程序设计竞赛(ACM)试题

E. Intersect

If a point P is on the segment AB and another segment CD at the same time, we say that P is an intersect point for AB and CD.

For two segments in two dimensions, how many intersect point do they have? Input

There are multiple test cases.

For each test case: the first line contains 4 integers represent th x-coordinate of point A, y-coordinate of point A, x-coordinate of point B, y-coordinate of point B, the second line contains 4 integers represent th x-coordinate of point C, y-coordinate of point C, x-coordinate of point D, y-coordinate of point D.

You can assume for all input integers v,-2<=v<=2, and A and B are always at different position,, C and D are always at different position, too. Output

For each test case:

If AB and CD have no intersect point , output a single line contains the string \If AB and CD have just one intersect point, output a single line contains the string \ If AB and CD have more than one intersect point (such as many), output a single line contains the string \Sample Input -2 -2 -2 -1 -2 -2 -2 2 -2 -2 -2 -1 -2 -2 -1 0 Sample Output Many One

F. Be Good at Gaussing

Give you many positive integer N (N<=23),for each N,just output N*(N+1)/2 integers in a single line,separated by space. (Don't ask me why.)For each N,the output line contains integers from 1 to N,and each just once.Again,do not ask me why,thank you.I'm so busy.But I can tell you a secret,the output has relationship with number triangle.As:(N=3) 1 2 6 3 4 5 See the sample for more information. Input

a positive integer N (N<=23). Output

For each N,output N*(N+1)/2 integers in a single line,separated by a blank space. Sample Input 3 4 2 6

Sample Output 1 2 6 3 4 5 1 2 9 3 10 8 4 5 6 7 1 2 3

1 2 15 3 16 14 4 17 21 13 5 18 19 20 12 6 7 8 9 10 11

G. A Multiply Problem

Our problem is,for a giving M rows and M columns matrix A, output another matrix B=AN. Input

For each test cases, there are two integers M and N in a single line. You can assume that 1<=M<=4,,0<=N<=4.

Then,M row M column integers value v followed. The ith row and jth column v represent a the ith row and jth column of matrix A. You can assume that for each v, -10<=v<=10. Output

Output M rows M columns integers represent the matrix B.

Each line of the output should contain M integers and these M integers should be separated by blank spaces. You must know no blank space after the last integer of each line. Sample Input 2 2 9 7 5 1

Sample Output 116 70 50 36

H. Count

Many ACM team name may be very funny, such as \minute here.

Is it \we can treat this name \For 5 'V's,our have 8 ways.They are:

1. V V V V V 2. V W W 3. W W V

4. V W V V 5. W V W 6. W V V V 7. V V W V 8. V V V W

The problem here is that for n 'V's,how many ways do we have to treat it?Because the answer may be too large, you should output the answer module by p.(If n is 0,then we have just

one way.) Input

There are multiple test cases. The first line of the input contains an integer M, meaning the number of the test cases.

For each test cases, there are two integers n and p in a single line. Output

For each test case, output the answer with case number in a single line. Sample Input 2 5 5 4 7

Sample Output 3 5