Programming Team:  Practice Contest, 21-Jan-05
Mt Lebanon HS 2004-5
David Kosbie

Link to the Programming Team Home Page.

Q1:  Read in three doubles:  x1, x2, and y2, followed by an integer n.  The doubles represent triangle T₁ which has vertices at (0,0), (x1,0), and (x2,y2).  Triangle T₂ is formed by connecting the midpoints of the sides of triangle T₁, and in general, triangle T_k+1 is formed by connecting the midpoints of the sides of triangle T_k.  Print out the perimeter of triangle T_n.

Q2:  Read in a positive integer n1 followed by a positive integer n2, where n2 > n1.  Print out the number of prime numbers in the range [n1,n2].  Note:  your program must run in under 1 second when n1=0 and n2 = 1 million.

Q3:  There are four unique digits a, b, c, and d such that the number abcd equals a^bc^d.  For example, the digits are not 2, 3, 4, 5 because 2³4⁵ equals 8 * 1024 which equals 8192, which does not equal 2345.  Find these digits and print out the number abcd.

Q4:  Read in an integer n>2, followed by n pairs of integers x_i,y_i which represent the vertices of a possibly-concave polygon.  The points are listed in clockwise order around the polygon, and you are guaranteed that the first and last pairs of points are identical.  Find the area of the polygon

Q5:   Read in an all-lowercase-letter string "s" and an integer "k" and print out the kth permutation of the letters in the string "s" when these permutations are listed uniquely in alphabetical order.