mhb@src.dec.com (Marc H. Brown) (06/03/91)
During Memorial Day Weekend, 330 students from 66 schools across
the country and Canada met at Cypress Creek HS in Houston, TX for
the 12th Annual Computer Science All-Star Contest sponsored by the
American Computer Science League (ACSL). The schools were invited
to participate based on their outstanding performance on ACSL's 4
regular season contests held at each school. About 400 schools
participated in each contest this year.
The All-Star Contest was composed of 2 parts: programming problems
in the morning, and computer science written tests in the afternoon.
The programming problems were solved as a team. Each team of 5 students
was given 3 computers with which to solve 5 problems. There was a
3 hour time limit. The written tests were solved by individual efforts.
Each of the 4 rounds comprised 3 problems from designated topics;
students had 15 minutes to complete each round.
One dozen Macinstosh SEs donated by Apple were awarded to the top
schools in each of the three divisions. Books, donated by
Addison-Wesley, Digital Press, Prentice-Hall, MIT Press, and John
Wiley were awarded to top students in each division.
The top schools in each division are listed below. An asterisk
indicates the school was awarded a computer.
Senior Division
(120 points max)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
107 * Montomery-Blair, MD
107 * Coral Gables, FL
98 * Barrington, RI
98 * N Miami Beach, FL
95 * Arlington, MA
93 * Evanston Township, IL
91 Illinois Math/Science, IL
90 AE Stevenson, IL
90 Beavercreek, OH
90 Langham Creek, TX
88 Jefferson Science/Tech, VA
88 W Torrance, CA
84 Emmaus, PA
83 Paul VI, VA
83 Libertyville, IL
81 Milford, NH
80 Enloe, NC
Intermediate Division
(120 points max)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
97 * Los Alamos, NM
88 * Alamo Hts, TX
78 * Freehold, NJ
76 * Cy-Fair, TX
74 Miami Sunset, FL
69 Cypress Creek, TX
68 Langham Creek, TX
66 Dunwoody, GA
62 E York, ON
55 Herbert Lehman, NY
55 N Toronto, ON
52 Conrad Weiser, PA
52 Auburn, MA
51 Enloe, NC
50 Miami Killian, FL
Junior Division
(60 points max)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
54 * Takoma Park, MD
52 * Jefferson Science/Tech, VA
50 Enloe, NC
48 Langham Creek, TX
40 Freehold,
It wouldn't be fair to networks around the world to reprint the contest
in its entirety here. You can obtain a copy by writing to ACSL, Box
40118, Providence, RI 02940. Here is one of the programming problems
("Farey Fractions") and a few of the written problems:
-------------------------------------------------------------------
Problem: The Farey sequence of order N is the ordered set
consisting of the fraction 0/1, followed by all irreducible proper
fractions with denominators from 2 to N, arranged in order of
increasing magnitude, followed by 1/1. Here are the first few
Farey sequences:
F1 = 0/1 1/1
F2 = 0/1 1/2 1/1
F3 = 0/1 1/3 1/2 2/3 1/1
F4 = 0/1 1/4 1/3 1/2 2/3 3/4 1/1
We use the notation FN;k to refer to the kth element of FN. For
example, F4;2=1/4and F3;4=2/3.
Input: Ten sets of data. Each set consists of a command string
followed two integers, a and b. The command string is either
"VALUE" or "LOCATE." We shall restrict ourselves to Farey sequences
of order 50 or less, and the first 5 inputs will involve Farey
sequences of order 10 or less.
Output: For VALUE commands, print the value of Fa;b as the the
numerator followed by the denominator. Both the numerator and
the denominator must be correct to receive credit. For LOCATE
commands, find the smallest Farey sequence containing an element
whose value is a/b. (We guarantee that there is such an element.)
Print the order of that Farey sequence and the position of the
element in the sequence. Both the order of that Farey sequence
and the position must be correct to receive credit.
Sample Input => Output
LOCATE, 2, 5 => 5, 5 (F5;5)
LOCATE, 45, 49 => 49, 695 (F49;695)
VALUE, 5, 8 => 2, 3 (2/3)
VALUE, 43, 385 => 19, 29 (19/29)
-------------------------------------------------------------------
-------------------------------------------------------------------
6. [Jr, Int, Sr] Bit String Flicking
Find all values of x (5 bits long) that satisfy the following
equation:
(LSHIFT-1 x) XOR (RCIRC-2 (RSHIFT-3 x)) = 10110
-------------------------------------------------------------------
9. [Jr, Int] Computer Number Systems
Binary multiplication can be implemented in terms of shifting
and adding. For example,
1011 110111 = 1011 + 10110 + 101100 + 10110000 + 101100000
sums 5 terms, 4 of which have been shifted. The product could
also be computed by summing 3 terms (110111, 1101110, and
110111000). To compute the product of A83C216 and E7D0016 by
shifting and summing the binary representation of both terms,
what is the fewest number of terms that must be summed?
-------------------------------------------------------------------
12. [Sr] Data Structures
Pick a node in a binary search tree. Delete it. Now, reinsert
that node. Let x be the number of nodes you could pick so that
the tree after the insertion is the same as before the deletion.
For a tree with 11 distinct nodes, what is the maximum value that
x could be?
-------------------------------------------------------------------
14. [Int, Sr] Pascal Programming
When the following program is run using the string All-Star! (9
characters long) as input, what are the final values-of variables
ltrCt and givenCt?
program AllStar91;
const
given = 'a';
var
ltrCt, givenCt: integer;
letter: char;
begin
ltrCt := 0; givenCt := 0;
repeat
read (letter);
if letter in ['a'..'z'] then
begin
ltrCt := ltrCt + 1;
if letter = given then
givenCt := givenCt + 1;
end;
until eoln;
end.
-------------------------------------------------------------------