Team Questions (SRU-style)

The following programs will be tested with redirection, as in q1.exe < testFile1.txt.

Question 1:  I'm in the Mode.  Read in a positive integer N followed by a set of N unordered integers.  Output the mode of the set -- that is, the element that occurs most frequently.  You are assured there will be a unique answer.

Question 2:  North by Northwest.  Read in a series of comma-delimited directions.  A direction is a one- or two-character sequence, and is one of N,S,E,W,NE,NW,SE,SW.  These will be terminated with a single period (".").  Thus, legal input might be:  "S,NW,S."  Assuming you begin at (0,0), and that north is up in the y-axis, and east is to the right in the x-axis (as you would expect), output a single line with two integers, the x,y position at which you end after following the directions in order.  For the "S,NW,S." example, the output would be "-1 -1".

Question 3:  Rascal's Triangle.  In Pascal's Triangle, as you all know, every row begins and ends with a 1, and every number between these 1's is the sum of the two numbers above that number in the triangle.  So the first row is "1", the second is "1 1", the third is "1 2 1", the fourth is "1 3 3 1", and so forth.  In Rascal's Triangle, you read in a number N, and each row begins and ends with N, and every number between these is the difference of the two numbers above.  So if N is, say, 3, then the first few rows are "3", "3 3", "3 0 3", "3 3 -3 3", and "3 0 6 -6 3".  Read in two integers, N and K (K >= 0), and output the Kth row of the Nth Rascal's Triangle, where the 0th row is just the number N.

Question 4:  Pass the Buck.  Read in a positive integer N followed by a possibly negative integer K.  You have N people in a circle with one person designated person 0 and who is holding a buck.  Once per second, if person B is holding the buck, he or she passes the buck to person (B+K) mod N (that is, K people to that person's right or left, depending on the sign of K).  Output a single number:  the number of clock ticks until everyone has been passed the buck.  Sometimes, this will never happen, in which case you should output "never".

Question 5:  Boxed In.  Read in 4 input lines each containing two floating point numbers separated by a space.  The two numbers represent a point (x,y) in a plane, and no number will occur twice in the input.  Thus, we can connect these 4 points to form a quadrilateral.  An integral point has integer coordinates.  Output a single integer:  the number of integral points that are fully contained within the quadrilateral (do not count points that lie on the perimeter).

Question 6:  Rambling Knight.  Say you have an R x C chess board -- that is with R rows and C columns.  A Knight's Tour is a series of legal Knight moves where the knight reaches every position on the board (but does not necessarily end where it started).  A Knight's Ramble is almost a Knight's Tour, but the Knight might skip a couple positions.  For this problem, a Knight's Ramble is described where the knight starts at row 0, column 0 (which is the top left, with rows increasing downward and columns increasing to the right).  Each position (x,y) contains an integer -- the step at which that position is reached in this tour, or -1 if it is skipped altogether.  One such knight's ramble could be:

0	9	4
3	-1	1
8	5	10
-1	2	7
6	11	-1

This knight's ramble has 5 rows and 3 columns.  The problem is, when the knight's ramble was input, the numbers were all entered top-to-bottom then left-to-right with no row delimiters, as in "0 9 4 3 -1 1 ...".  Worse, the input was padded with -1's at the back so that the number of positions is always a power of 2.  In this example, there are 5 rows and 3 columns, or 15 positions, so an extra -1 is added to give 16 total positions.  Thus, the input for this problem is:

    0 9 4 3 -1 1 8 5 10 -1 2 7 6 11 -1 -1

The problem is to read in such an input, and output 2 numbers, the number of rows and columns for which the input is a valid knight's ramble.  If there is more than one answer, print out the answer with the fewest columns.  In this example, of course, the answer is "5 3".

Good Luck!!!!

DK