1997 Mid-Atlantic Regional Programming Contest

Welcome to the
1997 Mid-Atlantic Regional Programming Contest
This packet contains the problem set for the contest. There are 7 contest problems.
Each person on a team should receive a copy of this packet.
Read the problem carefully and completely. If you submit a problem clarification, and
the answer to your question can be found in the problem specification, you will receive
the answer Read the specification.
The example presented with each problem statement is considered to be part of the
specification and may clarify some issues. Follow the output specifications closely and
use the sample output as a guide.
Most of the time, responses to a problem clarification will be sent only to the team
asking the question. If the judges deem it appropriate, the question and answer will be
sent to all teams.
The problem clarifications and problem submissions will occasionally get backed up.
They will be time stamped and processed in the order they are received. Do NOT sub-
mit a problem a second time unless you have received an answer to a previous submis-
sion. Do NOT send problem clarifications asking where your response is.
You may NOT use any other software resources than those officially provided (com-
pilers, debuggers, etc.). For example, you may NOT use LEX or YACC to assist in the
development of a contest solution. Your activities will be monitored and teams that
violate these rules will be disqualified.
The judges use their own test data to evaluate your submissions. The fact that your
program works on the example in the problem specification does not necessarily mean
it will work against the judges test data.
The judges decisions are final.
1997 Mid-Atlantic Regional Programming Contest
Problem A
Lax Security
Problem Statement
The Lax Hazardous Waste Company has o have a certain amount of security at their plant
because of the nature of the materials they manage. The main door to the plant has a keypad
similar to the one shown below. To open the door, and employee must first enter his or her 5-
digit personal identification number (PIN). If the PIN is valid, the door opens.
However, Bocefus Lax, the owner of the company, is a nice guy and doesnt like to burden his
employees unnecessarily. The digits on the keypad are close together and employees often
enter their PIN incorrectly by pressing an adjacent button instead of the intended one. There-
for, he wants to modify the access system so that it allows an employee to open the door even
if the PIN that is entered is slightly incorrect. Specifically, Bocefus is willing to assume that the
person using the keypad is a valid employee if the number entered has no more than one digit
that is off-by-one from any valid PIN. In this context, off-by-one means that the incorrect digit
is adjacent to the correct one on the keypad in one of the four primary directions (but not diag-
onally). Adjacency does not wrap. For example, 4 is adjacent to 1, 5, and 7 only.
Write a program to help Bocefus by determining if a set of PINs are valid under this new,
relaxed system. You are initially given a list of valid PINs that permit entry. Then you are
given a list of numbers that have been entered on the keypad. Your job is to report that the
number entered is either accepted or rejected. If accepted, report which valid PIN it matches
(exactly or approximately).
Note that in this new system a number entered on the keypad could be matched to more than
one valid PIN. For example, the PIN 22222 is off-by-one from 21222, 52222, and many others.
If the number entered matches a PIN from the valid list exactly, report that match. If there is no
exact match, and two or more PINs match the number entered approximately, then report the
first PIN in the valid list that applies.
1 2 3
4 5 6
7 8 9
0
Input
The first line of input contains a single integer N representing the number of valid PINs pro-
vided. Each of the next N lines of input contain one valid PIN. The next line of input contains
a single integer M representing the number of PINs to test. Finally, each of the next M lines of
input contains one PIN to evaluate.
The value for N will be in the range 1 to 100, inclusive, and the value for M will be in the range
1 to 20, inclusive. All PINs, including the test PINs, are made up of a sequence of exactly 5
digits between 0 and 9, inclusive.
Output
For each test PIN in the input, print a single line of output that consists of the PIN tested, he
word VALID or INVALID, and, if the PIN was determined to be valid, the PIN to which it was
matched.
At the end of the output, print the phrase END OF OUTPUT on a line by itself.
Example
The following sample input should produce the output shown
Sample Input Sample Output
10
10360
74288
39491
20457
64973
99999
54385
36491
87873
33899
6
54385
48484
62673
20158
28457
36491
54385 VALID 54385
48484 INVALID
62673 VALID 62973
20158 INVALID
28457 VALID 20457
36491 VALID 36491
END OF OUTPUT
1997 Mid-Atlantic Regional Programming Contest
Problem B
NYPD Cordon Blue
Problem Statement
Despite recent efforts to curb crime in New York City, its still a big problem. Furthermore,
economic pressures are forcing public officials, like the Chief of Police, to adopt some tough
policies.
When officers of the New York police department arrive at a crime scene, their first task is to
cordon off the area with yellow tape to keep the public away. The tape must encompass all
pieces of evidence. The Chief has decided that the officers should use no more tape than neces-
sary.
Your job is to write a program to compute the minimal amount of tape necessary to cordon off
a crime scene. You are provided with the coordinates of all pieces of evidence. The officers
first choose an arbitrary origin for their coordinate system. Then the positions of all pieces of
evidence are noted relative to that origin. The coordinate system represents square feet.
You may assume there will be at least two pieces of evidence. For the sake of calculation, you
may assume that a piece of evidence has no area to take into account. Therefore, to cordon off
a crime scene, the yellow tape must be extended in a loop from one piece of evidence to
another, then another, and so on, eventually reaching the first piece of evidence, such that all
pieces of evidence are in or on the loop.
Input
The first line of input contains a single integer N representing the number of crime scenes to be
cordoned off. The remaining lines of input data define the crime scenes. The first line of data
for each crime scene contains a single integer M representing the number of pieces of evidence
at that scene. Each of the next M lines of input contains two integers, X and Y, separated by 1
space, indicating that the piece of evidence is located at position <X, Y> relative to the arbi-
trary origin.
The value for N will be greater than or equal to 1. The value for M for each crime scene will be
in the range 2 to 100, inclusive. The values for X and Y will be in the range 100 to 100, inclu-
sive.
Output
For each crime scene, print the phrase CRIME SCENE Z:, where Z is the number of the crime
scene (starting with 1), followed by the minimal length of the yellow tape, followed by the
units (feet). All values for the tape length should be presented to three decimal places of preci-
sion.
At the end of the output, print the phrase END OF OUTPUT on a line by itself.
Example
The following sample input should produce the output shown
Sample Input Sample Output
3
6
9 -4
2 7
4 4
7 9
-5 9
2 4
11
-7 12
2 11
-10 -10
-9 17
11 6
5 -3
0 0
6 7
-3 4
-6 -3
5 -11
2
-4 5
1 5
CRIME SCENE 1: 44.258 feet
CRIME SCENE 2: 82.905 feet
CRIME SCENE 3: 10.000 feet
END OF OUTPUT
1997 Mid-Atlantic Regional Programming Contest
Problem C
Royal Threat
Problem Statement
Chess pieces move in varied and interesting ways. For example, knights perform L-shaped
moves, as defined by the diagram below. That is, if a knight is in the position marked with the
K, then it can move to any position containing a ~ assuming that the new location is on the
board. Therefor, if there is another piece in any of the positions marked with a ~, then the
knight at position K is said to be threatening that piece. In general, we say that a chess piece
threatens another if it can move to that position (and therefore capture the other piece) in one
step.
A king can move in any of the eight directions (forward, back, right, left, and the diagonals),
one position at a time. Therefore, a king threatens any piece in the eight positions directly adja-
cent to it.
A rook can move in any of the four primary directions (forward, back, right, and left) as many
positions as desired, except that it cannot jump over any other piece. Therefore, a rook
threatens the first piece encountered in each of those four directions.
A bishop is similar to a rook, except that it can move in any of the four diagonals. Therefore, a
bishop threatens the first piece encountered in each of the diagonal directions.
A queen can move in any of the eight directions, as many as desired. It also cannot jump
other pieces. Therefor, a queen threatens the first piece encountered in each of the eight possi-
ble directions.
For this problem, assume that there are an unlimited number of knights, kings, rooks, bishops,
and queens. Also assume that the color of the pieces does not matter.
Write a program that, given the positions of a set of arbitrary chess pieces, determines how
many of those pieces are threatened by at least one other piece.
~ ~
K
~ ~
~
~
~
~
The board is a standard eight by eight grid. To specify a particular position, we will refer to its
row number (1 through 8) and its column number (1 through 8). The position at row 1 and col-
umn 1 is in the upper right corner of the board.
Input
The first line of input contains a single integer N that represents the number of board configu-
rations to process. For each configuration, the first line of input contains a single integer M that
represents the number of chess piece on that board. Each of the next M lines for each configu-
ration contains the type and location of a chess piece. The first character indicates the type of
the chess piece, as follows: K=knight, Q=queen, B=bishop, R=rook, and G=king, followed by
a single space. The rest of the line contains two integers representing the row and column of
that piece, separated by one space.
All row and column values will be within the range 1 to 8, inclusive. The positions of all pieces
in each test case will be distinct (each position can hold only one piece). The value of N will be
greater than or equal to 1 and the value of M will be in the range 1 to 64, inclusive.
Output
The output for each test case should begin with the phrase CONFIGURATION Z:, where Z is
the board number (starting with 1), followed by the number of unique pieces threatened, fol-
lowed by the phrase PIECES THREATENED.
At the end of the output, print the phrase END OF OUTPUT on a line by itself.
Example
The following sample input should produce the output shown
Sample Input Sample Output
2
6
R 2 2
B 3 6
K 4 4
G 5 4
R 6 5
R 7 3
10
Q 2 2
B 4 2
B 5 2
B 6 2
B 7 2
K 2 8
R 4 7
G 5 5
G 7 5
G 8 8
CONFIGURATION 1: 4 PIECES THREATENED
CONFIGURATION 2: 4 PIECES THREATENED
END OF OUTPUT
1997 Mid-Atlantic Regional Programming Contest
Problem D
FUN Programming
Problem Statement
The Fundamentally Unnecessary (FUN) programming language is defined below. Your job is
to write a program that will read a FUN program, determine if there are any syntax errors, and
if no errors exist, execute the program.
The keywords of the FUN programming language are: start, end, loop, endloop, bool,
endbool, and out. All keywords are given in lowercase letters and cannot be used as vari-
ables.
A FUN program begins with the keyword start and terminates with the keyword end. Zero
or more additional program statements can exist between the start and end delimiters of a pro-
gram. A program statement is any one of the following: assignment statement, output state-
ment, conditional statement, or repetition statement.
An assignment statement consists of a variable followed by the = operator, followed by an
expression. When executed, the expression is evaluated and the result is stored in the variable.
An expression can be a term or it can take the form term + expression, where the + operator
represents integer addition. A term is either an integer literal or a variable.
An integer is a word consisting of one or more lowercase letters (a through z). You may
assume that variable will be no longer than 25 characters. Each variable in a FUN program
stores a single integer value. Variables are not declared, and contain zero initially. When a vari-
able is referenced in an expression or condition, the current value of the variable is used.
An output statement consists of the keyword out followed by an expression or a string literal.
When executed, it prints the value of the expression or the string literal, then moves to the next
line.
A string literal is zero or more characters delimited on both ends by the quote (") character. A
string literal cannot be split over multiple lines. You may assume that a string literal will not
contain the quote character.
A conditional statement begins with the keyword bool, followed by a condition, followed by
the condition body, and is terminated by the keyword endbool. When executed, the condition
is evaluated, and if the condition is true, the condition body is executed. If the condition is
false, processing continues with the statement after the endbool terminator. A condition
body is zero or more program statements.
A condition has the form expression < expression, where < is the less-than operator. When
evaluated, both expressions are evaluated to integer values, and if the first value is less than the
second, the condition is true. If not, the condition is false.
A repetition statement begins with the keyword loop, followed by an expression, followed by
the loop body, and is terminated by the keyword endloop. When executed, the expression is
evaluated, producing an integer result X, if X is greater than 0, the loop body is executed
exactly X times, otherwise it is not executed at all. A loop body is zero or more program state-
ments.
White space is defined to be one or more space characters and/or line terminators. You may
assume that white space exists between any two language elements, except around operators
(where it may or may not exist).
An error is defined as any violation of the above rules. If you were told you could assume
something, then the data will follow that assumption.
Input
The first line of input consists of a single integer N that represents the number of FUN pro-
grams to process. The rest of the lines of input consist of N FUN programs, delimited by the
start and end keywords. You may assume that the programs are delimited correctly and that
there are no extra uses of the start and end keywords in any program.
The value for N will be greater than or equal to 1. There will be no more than 100 lines in each
FUN program. There will be no more than 100 unique variables used in each FUN program.
Output
For each program, print the statement PROGRAM Z: where Z is the number of the program
(start counting with1). If there are any errors in the program, print the statement ERRORS
EXIST. If there are no errors, print the output of the program. Put a blank line between the out-
put for each program.
At the end of the output for all programs, print the phrase END OF OUTPUT on a line by
itself.
Example
The following sample input should produce the output shown
Sample Input Sample Output
3
start
count = 14
bool count < 25
out "Count is"
out count
endbool
out "Example 1 done."
end
start
num = -3
loop 6
out num
bool num < 0
out "Num is negative."
sum = sum + num
endbool
num = num+1
endloop
out "Sun is"
out sum
end
start
value = 25
bool value > 45
value = value * 2
endbool
end
PROGRAM 1:
Count is
14
Example 1 done.
PROGRAM 2:
-3
Num is negative.
-2
Num is negative.
-1
Num is negative.
0
1
2
Sum is
-6
PROGRAM 3:
ERRORS EXIST
END OF OUTPUT
1997 Mid-Atlantic Regional Programming Contest
Problem E
Word Morphing
Problem Statement
When you were a child you may have come across the classic word morphing game. In the
game you are given two common words (which could be found in a dictionary) both having 5
characters each. You start with the first word given, and perform a one character transforma-
tion on that word, forming a new word which must also be found in the dictionary. This pro-
cess continues until your reach the second word that you were originally given or until you
have determined that the second word can not be formed.
For example, given the pair beers and dealt, a valid sequence might be:
beers
beets
meets
meats
meals
seals
deals
dealt
The alphabet is defined to be the set of all lowercase letters (a through z). All dictionary words
will be exactly five characters long. A valid transformation is the process of replacing any one
character in the word with any one character from the alphabetic, resulting in a word that is in
the dictionary.
Write a program that accepts a set of words that make up the dictionary and a list of word pairs.
For each pair, determine if sequence can be formed from the first word in the pair to the second
word in the pair.
Input
The first line of input contains a single integer value N which represents the number of words
in the dictionary. Each of the next N lines contains one dictionary word, starting in the first col-
umn. The next line contains a single integer M representing the number of word pairs to evalu-
ate. Each of the next M lines contains two words, separated by one space. The first word on the
line is the starting word of the sequence, and the second word on the line is the last word of the
sequence.
The value of N will be in the range 1 to 200, inclusive. The value of M will be in the range 1 to
25, inclusive. Each word in the dictionary will composed of exactly five letters from the alpha-
bet. Each word in the word pairs to evaluate will be valid words from the dictionary. The dic-
tionary words will not be listed in any particular order.
Output
For each pair of words evaluated, print the phrase PAIR Z:, where Z is the number of the test
set (starting at 1), followed by the pair of words.
If no valid transformation sequence exists, print the phrase NO SEQUENCE. If a sequence
does exist, print each word in the sequence, in order, from the start word to the end word, each
on its own line. You only should print one sequence, even if multiple sequences exists.
Separate the output for each pair of words examined with a single blank line. At the end of the
output, print the phrase END OF OUTPUT.
Example
The following sample input should produce the output shown
Sample Input Sample Output
24
agony
alive
built
creep
allay
dress
chili
creed
alley
crepe
align
cress
alone
abash
crest
break
alike
build
child
abase
chill
along
creak
crept
3
align along
built alley
crept dress
PAIR 1: align along
align
alike
alive
allay
alley
alone
along
PAIR 2: built alley
NO SEQUENCE
PAIR 3: crept dress
crept
crest
cress
dress
END OF OUTPUT
1997 Mid-Atlantic Regional Programming Contest
Problem F
Pest Control
Problem Statement
The professors at Dubious University must have their offices fumigated due to the emergence
of cockroaches. The university has contracted with Croakem, Inc., a company that specializes
in extermination, to handle the job.
Croakem uses a highly toxic chemical called ethlydiethoxyphosphinylformate to handle the
job. The chemical is so toxic that special care must be taken to determine the amount of air
space affected in order to mix the formula with exactly the right amounts of primary ngredi-
ents. Too little or too much of any part will cause serious health risks.
Ethlydiethoxyphosphinylformate is made up of three primary ingredients: six parts methoxy-
flavone, 1 part pyridineboran, and three parts tetrapropylzirconate. That is:
ethlydiethoxyphosphinylformate = 0.60 * methoxyflavone +
0.10 * pyridineboran +
0.30 * tetrapropylzirconate
The amount of each primary ingredient (in grams) is determined by the following functions:
methoxyflavone = e
3
( / 4) + (x
2
/ 55)
pyridineboran = * ( )
2
tetrapropylzirconate = 7.24 + (69 * ) ((4 * ) / 2)
where is the volume of air space in the room in cubic feet, e is the equal to 2.718281828, is
equal to 3.141592654, and , , and are constants equal to 3.534, 6.104, and 1.33387 respec-
tively. We defer the explanation of these formula until another time. Its technical.
Write a program to compute the amount of ethlydiethoxyphosphinylformate that should be
used for a series of offices. You are given the dimensions of each office and the dimensions of
each piece of furniture in each office. The volume of the air space in the room is defined as the
volume of the office minus the sum of the volumes of the furniture in the office. You may
assume that the computed air space in the room will be no larger than 600 cubic feet.
Input
The first line of input contains a single integer N representing the number of offices to be fumi-
gated. The rest of the input is the data on the offices. The first line of input for each office con-
tains three integers corresponding to the length, width, and height of the office. The second
line of input for each office contains a single integer M indicating how many pieces of furni-
ture are in the office. Each of the next M lines of data for the office contains three integers rep-
resenting the length, width, and height of a piece of furniture in the office.
The value for N will be in the range 1 to 50, inclusive, and the value for M will be in the range
1 to 10, inclusive. All length, width, and height measurements are given in feet.
Output
For each office, print the phrase OFFICE Z:, where Z is the number of the office tested (start-
ing at 1), followed by the calculated amount of ethlydiethoxyphosphinylformate, followed by
the units (GRAMS). Print the amount to three decimal places of precision. If the computed
amount of the chemical is less than zero, print 0.0 GRAMS (the hugs will apparently die on
their own).
At the end of the output, print the phrase END OF OUTPUT on a line by itself.
Example
The following sample input should produce the output shown
Sample Input Sample Output
2
10 10 5
3
2 2 2
5 2 8
3 4 1
3 15 8
6
1 1 2
5 10 2
2 1 1
4 3 2
3 3 3
4 4 1
OFFICE 1: 22749.785 GRAMS
OFFICE 2: 5015.737 GRAMS
END OF OUTPUT
1997 Mid-Atlantic Regional Programming Contest
Problem G
Spacely Sprockets Teleport System
Problem Statement
The year is 2112. Due to the lack of oil reserves, combustion engines are a thing of the past.
People have relied on foot power and animal-pulled methods of transportation for more than
75 years. But now, the Spacely Sprockets Corporation (SSC) is on the verge of a new mode of
transportation.
SSC has developed a teleportation system to move people from one building to another. The
system consists of a starting pad and an ending pad. Items placed on the starting pad can be
teleported to the corresponding ending pad, but it is a one-way system.
In order to test the system, Spacely Sprockets has placed a number of the pads at their various
corporate buildings. Quality assurance officer George Jetson must travel to all of the buildings
so that he can test the system. In fact, the system is so close to completion that the company
has begun to take sales orders for it. So George needs to test the system in each of several cit-
ies.
Your job is to assist George in planning his test jumps. Given a map of the system in each city,
find a series of teleports that George can make such that he reaches all of the locations. He may
have to pass through a location more than once to reach all offices. Note that he doesnt need to
test every teleport possibility, but he must reach each building in the system.
System maps for each city will be given in the form of an adjacency matrix. An adjacency
matrix M for a particular city with n buildings is an n
2
matrix of zeroes and ones where for all
i and j from 1 to n, M(i, j) is 1 if and only if the city has a transport system from building i to
building j. A system such as:
would be described by the following adjacency matrix:
0 1 0 0
1 0 1 1
1 0 0 0
0 0 0 0
building 1
building 2
building 3
building 4
george always starts at the main building (number 1) in each city. There may be multiple paths
to reach all of the buildings, but you may report any one of them. However, do not repeat loops
through the system of buildings unnecessarily.
Input
The first line of input contains a single integer N which represents the number of cities in
which there are systems to evaluate. For each city, the first line of data contains a single integer
M which represents the number of buildings in the city. The next M lines contain the adjacency
matrix for the city.
The entries on each line of an adjacency matrix are separated by a single space character. The
value of N will be in the range 1 to 20, inclusive. The value of M will be in the range 2 to 50,
inclusive.
Output
For each city tested, print the CITY Z:, where Z is the number of the city (starting at 1).
If there is no path that George can travel to reach all buildings, print the phrase NO PATH. If
there is a path, print the building numbers (in order) that George can visit to reach all of the
buildings.
Print a single blank line after the output for each city. At the end of all of the output, print the
phrase END OF OUTPUT on a line by itself.
Example
The following sample input should produce the output shown
Sample Input Sample Output
2
4
0 1 0 0
1 0 1 1
1 0 0 0
0 0 0 0
5
0 1 0 1 0
0 0 1 0 1
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
CITY 1:
1 2 3 1 2 4
CITY 2:
NO PATH
END OF OUTPUT