Make your own free website on Tripod.com
Agawam Programming Team

Home

More Info
Getting Started
2001-2002 Competition
2001-2002 Questions
2001-2002 Questions

Western New England College
Seventeenth Annual Invitational
High School Programming Contest
 
March 15, 2002

1) Pinball Wizardry
A pinball machine has three horizontal beams B1, B2, and B3 of length 5 upon which a pinball will hit and roll.  Each of the beams has a hole cut in it through which the pinball will fall, which are at locations H1-H3, where H is an integer and 0<H<5.  Furthermore, each bar is blocked at the ends so that the inball can't rool off, but instead will bounce off and roll in the opposite direction.  The pinball always hits the first beam B1 at the location 0 and proceeds to rool right toward the end at location 5.  Eventually it drops through the hole at location H1 and onto beam B2.  Depending on where the hole on B2 is, it either drops through H2 immediately, continues rolling towards the right until it drops through H2, or rolls all the way to the end, bounces off the blocked end, and then rolls the other way until it drops through H2 onto B3.  This process continues on B3 until the ball finally drops through the hole H3. 
 
Write a program which reads a set of three values H1, H2, and H3 (one per line), calculates how far the pinball rolls, and ouptuts that total distance.
 
2) Sampling Digits
Digital Recording devices (such as a MP3 recorder)must sample a signal and measure/record it using the closest possible value having a certain fixed percision.  This is analogous to using a ruler to measure the width of your index finger.  Suppose the actual width was .5678.  With a precision of 1/2 units, the recorded measurement would be .5.  With a percision of 1/4 units, the recorded measurement would again be .5 (because the range of values is {0, .25, .5, .75, 1.}  Wigh a percision of 1/8 units, the recorded measurement would be .625 (because the range of values is {0., .125, .25, .375, .5, .625, .75, .875, and 1.}.
 
Write a program which simulates a digital recorder.  It should first read in a number p which will always be a power of two between 2 and 1024.  This number p represents the degree of percision, which means the possible values will range from {0., 1/p, 2/p, ...,1.} Then it should read a number between 0. and 1. to be sampled and output the recorded measurement.
 
3) Thwarting a Hacker
A hacker has broken into your school's computer system and changed several user's passwords who had (unwisely) used passwords composed only of three alphabetic lowercase characters (for example, their initials).  From the clues you have been able to gather, you've deduced that the hacker encripted the passwords using a classic (used by Caesar) substitution cipher.  Each of the three alphabetic letters a-z was right circularly shifted by n letters to produce another alphabetic letter.  For example, the password "acb" right circularly shifted by four letters yields "egf".  The same cipher applied to the password "zvy" yields "dzc" after right circularly shifting by four letters.
 
Your job is to write a program which helps finds the encrypted passwords.  It should accept as input the original three character password, and the number n (0<n<26) of characters for the right circular shift.  It should then output the encrypted password.
 
4) Half a Pair o' Dice
A die (one half of a pair of dice) is a cube with faces numbered one through six (depicted with dots).  These faces have the property that the sum of each face and it's opposite equals seven.
 
Write a program which simulates the rolling of a die.  The program should read in the initial value for the top face and the value of the next face which would be on top, as the die rolls in a  forward direction.  On the next line, a number n>2 will be given which indicates how long the die rolls (counted as the total number of faces appearing on top, including the first one and last one).  The program should print out the last number showing on the top face when the die has finished rolling.
 
5)  Diagonal Arrangement
Consider a square array of integers composed of n rows and n columns, for example with n=3
 
 1     3     5
 7     9     11
13    15   17
 
This array has the following 5 diagonals, listed one per line as follows
 
5
3     11
1     9     17
7     15
13
 
Write a program which reads in the number n, between 2 and 20. It then reads n values per row for the next n rows.  It then outputs the diagonals one per line.
 
6)  Triangle Strips
In graphics applications, 3D objects are typically composed of large meshes of triangles.  For interactive applications (such as video games) fast rendering requires that the triangles be organized into long strips where each triangle in a strip shares two of its three vertices with the next triangle.  Consider the strip composed of the four triangles described by the sets of vertices {2, 4, 5}, {5, 1, 2}, {1, 6, 2}, {6, 3, 1}.  According to convention, each vertex is identified by a unique integer and each triangle is described by a list of its three vertices.  The most compact and efficient way to describe this strip is to list each vertex only once.  Since each triangle shares two of its three vertices with each adjacent triangel in the strip, these two shared vertices need not be repeated.  For example in problem 4, the optimized triangle strip list would look like this
 
4  5  2  1  6  3
 
Write a program which accepts as input the number n of vertices in the strip.  The program should then read in the three integers representing the vertices of each tringale, three per line.  It should then output the optimized triangle strip list.
 
7)  The Other List
Linked lists are powerful data structures in computer programming.  There are many ways to represent linked lists.  In languages that support dynamic structures, such as C/C++, linked lists can be defined by using pointers.  A method supported by all programming languages is to use a table to represent a linked list.  Each row of the table contains an element of the list, and the index of the next element.  For the last element of a list, the index of its next element is 0.  We can actually put several lists in one table.  For example, the following table
 
1     A     7
2     C     0
3     G     6
4     D     0
5     X     9
6     B     1
7     I     0
8     M     2
9     F     8
 
represents three lists:
     List 1:   G -> B -> A -> I
     List 2:   X -> F -> M -> c
     List 3:   D
 
You are to write a program that reads a table and reverses all lists in the table.  The first data line contains an integer, n, representing the size of the table.  You may assume that 1 < n < 30.  Each of the next n data lines contains an uppercase letter indicating a list element and an integer indicating the index of next element on the same list.  Note that when you reverse a list, change only the index of each element, but don't move any element.
 
Note that after you reverse all lists, they would become
     List 1:     I -> A -> B -> G
     List 2:     C -> M -> F -> X
     List 3:     D

Any questions or comments can be sent to the webmaster at towert77@attbi.com