|
|||||||
|
|
|
|||||
|
|
|||||||
20 August, 2002 9:00am - 7:00pm
PROBLEM No. 1
Credit: 100
Points
The Center City fire department collaborates with the
transportation department to maintain maps of the city, which reflects the
current status of the city streets. On any given day, several streets are
closed for repairs or construction.
Firefighters need to be able to select routes from the fire stations to
fires that do not use closed streets.
Central City is divided into non-overlapping fire districts, each
containing a single fire station. When a fire is reported, a central dispatcher
alerts the fire station of the district where the fire is located and gives a
list of possible routes from the fire station to the fire. You must write a
program that the central dispatcher can use to generate routes from the
district fire stations to the fires.
Input and Output
The city has a separate map for each fire district. Street corners
of each map are identified by positive integers less than 21, with the fire
station always on corner #1. The input file contains several test cases
representing different fires in different districts. The first line of a test case consists of a single integer, which
is the number of the street corner closest to the fire. The next several lines
consist of pairs of positive integers separated by blanks, which are the adjacent
street corners of open streets. (For example, if the pair 4 7 is on a line in
the file, then the street between street corners 4 and 7 is open. There are no
other street corners between 4 and 7 on that section of the street.) The final
line of each test case consists of a pair of 0s.
For each test case, your output must identify the case by number
(case #1, case #2, etc). It must list each route on a separate line, with the
street corners written in the order in which they appear on the route. And it must
give the total number routes from fire station to the fire. Include only routes, which do not pass
through any street corner more than once.
(For obvious reasons, the fire department does not want its trucks
driving around in circles.) Output from separate cases must appear on separate
lines.
TEST CASES:
Input Output
6 CASE 1:
1
2 1 2 3 4
6
1
3 1 2 3 5
6
3
4 1 2 4 3
5 6
3
5 1 2 4 6
4
6 1 3 2 4
6
5
6 1 3 4 6
2
3 1 3 5 6
2
4 There are 7 routes from the
fire station to street corner 6.
0 0
CASE 2:
4 1 3 2 5
7 8 9 6 4
2
3 1 3 4
3 4 1 5 2 3
4
5
1 1 5 7 8
9 6 4
1
6 1 6 4
7
8 1 6 9 8
7 5 2 3 4
8
9 1 8 7 5
2 3 4
2
5 1 8 9 6
4
5
7 There are 8 routes from the
fire station to street corner 4.
3 1
1 8
4 6
6 9
0 0
=============================================================================
PROBLEM No. 2
Credit: 50 Points
Your little sister Chanchal has just learned about palindromes and
anagrams and is hell bent upon enlightening you about things like "Rats live on no evil star.” You are
known to be a great wizard with computers and she now wants you to write a
program that will help her find palindromes.
Your program should read in a character string and print out the
longest sub string that is a palindrome. Note that the length of the longest
palindrome cannot be less than 1.
The exact input and output format is specified below:
TEST CASE:
Input
qghgqfjhfjj8947fkj55hh5jh5h5545h4k5hkh53434hg4gh43435hkh5k4h5455hhg55h5kjh5
Output
h5545h4k5hkh53434hg4gh43435hkh5k4h5455h
=============================================================================
PROBLEM No. 3
Credit: 200 Points
Consider
the points on an infinite grid of equilateral triangles as shown
below:
x
x x
x x x
x x x x
x x x x x
.
.
Note that if we number the points from left to right and top to
bottom, then groups of these points form the vertices of certain geometric
shapes. For example, the sets of points {1,2,3} and {7,9,18} are the vertices
of triangles, the sets {11,13,26,24} and {2,7,9,18} are the vertices of
parallelograms.
Write a program, which will repeatedly accept a set of points on
this triangular grid, analyze it, and determine whether the points are the
vertices of one of the following acceptable figures:
triangle,
parallelogram,
In order for a figure to be acceptable, it must meet the following
two conditions:
1)
Each
side of the figure must coincide with an edge in the grid.
2) All sides of the
figure must be of the same length.
Input and Output
The input will consist of an unknown number of point sets. Each
point set will appear on a separate line in the file. There are at most six
points in a set and the points are limited to the range 1..32767.
For each point set in the input file, your program should deduce from
the number of points in the set which geometric figure the set potentially
represents; e.g., Four points can only represent a parallelogram, etc. The
output must be a series of lines listing each point set followed by the results
of your analysis.
TEST CASE:
Input Output
1 2
3 1 2 3 are the vertices of
a triangle
11 13
29 31 11 13 29 31 are not the
vertices of an acceptable figure
26 11
13 24 26 11 13 24 are the vertices
of a parallelogram
1 2 3 4
5 1 2 3 4 5 are not the vertices
of an acceptable figure
47 47 are not the vertices of an
acceptable figure
11 13
23 25 11 13 23 25 are not the
vertices of an acceptable figure
=============================================================================
PROBLEM No. 4
Credit: 250 Points
County General Hospital is trying to chart its course through the
troubled waters of the economy and shifting population demographics. To support the planning requirements of the
hospital, you have been asked to develop a simulation program that will allow
the hospital to evaluate alternative configurations of operating rooms,
recovery rooms and operations guidelines. Your program will monitor the usage
of operating rooms and recovery room beds during the course of one day.
County General Hospital has several operating rooms and recovery
room beds.
Each surgery patient is assigned to an available operating room
and following surgery the patient is assigned to one of the recovery room beds. The amount of time necessary to transport a
patient from an operating room to a recovery room is fixed and independent of
the patient. Similarly, both the amount of time to prepare an operating room
for the next patient and the amount of time to prepare a recovery room bed for
a new patient are fixed.
All patients are officially scheduled for surgery at the same
time, but the order in which they actually go into the operating rooms depends
on the order of the patient roster. A patient entering surgery goes into the
lowest numbered operating room available. For example, if rooms 2 and 4 become
available simultaneously, the next patient on the roster not yet in surgery
goes into room 2 and the next after that goes into room 4 at the same time.
After surgery, a patient is taken to the available recovery room bed with the
lowest number. If two patients emerge
from surgery at the same time, the patient with the lower number will be the
first assigned to a recovery room bed.
(If in addition the two patients entered surgery at the same time, the
one first on the roster is first assigned a bed.)
Input and Output
The input file contains data for a single simulation run. All numeric data in the input file are
integers, and successive integers on the same line are separated by
blanks. The first line of the file is
the set of hospital configuration parameters to be used for this run. The parameters are, in order:
Number of operating
rooms (maximum of 10)
Number of recovery room
beds (maximum of 30)
Starting hour for 1st surgery of day (based on a 24-hour clock)
Minutes to transport
patient from operating room to recovery room
Minutes to prepare
operating room for next patient
Minutes to prepare
recovery room bed for next patient
Number of surgery
patients for the day (maximum of 100)
Pairs of lines of patient data will follow this initial
configuration data as follows:
Line 1: Last name of patient (maximum of 8 characters)
Line 2: Minutes required for surgery Minutes required in the recovery room
Patient records in the input file are ordered according to the
patient roster, which determines the order in which patients are scheduled for
surgery. The number of recovery room
beds specified in any configuration will be sufficient to handle patients
arriving from surgery (No queuing of patients for recovery room beds will be
required). Computed times will not extend past 24:00.
Correct output shows which operating room and which recovery room
bed is used by each patient, and the time period that the patient uses the room
and bed along with a summary of the utilization of hospital facilities for that
day. The output file consists of a set
of two tables describing the results of the simulation run. The first table is in columnar form with
appropriate column labels to show the number of each patient (in the order the
patient roster), the patients last name, the operating room number, the time
surgery beings and ends, the recovery bed number and the time the patient
enters and leaves the recovery room bed.
The second table will also be in columnar form with appropriate
column labels summarizing the utilization of operating rooms and recovery room
beds. This summary indicates the facility type (room or bed), the facility
number, the number of minutes used and percentage of available time utilized.
Available time is defined as the time in minutes from the starting time for 1st
surgery of day to the ending time of the last patient in a recovery room bed.
A sample input file and corresponding correct output are shown
below.
TEST CASE:
Input Output
5 12 7
5 15 10 16 Patient Operating Room Recovery Room
Jones # Name Room# Begin
End Bed# Begin
End
28
140 ------------------------------------------------------
Smith 1 Jones 1 7:00
7:28 3 7:33
9:53
120
200 2 Smith
2 7:00 9:00
1 9:05 12:25
Thompson 3 Thompson 3 7:00
7:23 2 7:28
8:43
23
75 4 Albright
4 7:00 7:19
1 7:24 8:46
Albright 5 Poucher 5 7:00
9:13 5 9:18
12:47
19
82 6 Comer
4 7:34 8:48
4 8:53 10:34
Poucher 7 Perry 3 7:38
9:11 2 9:16
12:24
133
209 8 Page
1 7:43 9:34
6 9:39 13:22
Comer 9 Roggio 4 9:03
10:12 9 10:17
12:19
74
101 10 Brigham 2
9:15 9:57 8
10:02 11:21
Perry 11 Nute 3 9:26
9:48 7 9:53
11:04
93
188 12 Young
5 9:28 10:06
3 10:11 12:31
Page 13 Bush 1
9:49 10:15 10
10:20 12:21
111
223 14 Cates
3 10:03 12:03
8 12:08 16:16
Roggio 15 Johnson 2 10:12
11:38 4 11:43
14:44
69
122 16 White
5 10:21 11:53
7 11:58 14:18
Brigham
42 79
Nute Facility Utilization
22
71 Type # Minutes
% Used
Young -------------------------
38
140 Room 1
165 29.68
Bush Room 2
248 44.60
26
121 Room 3
258 46.40
Cates Room 4
162 29.14
120
248 Room 5
263 47.30
Johnson Bed 1 282 50.72
86
181 Bed 2
263 47.30
White Bed 3
280 50.36
92
140 Bed 4
282 50.72
Bed 5
209 37.59
Bed 6
223 40.11
Bed 7
211 37.95
Bed 8 327
58.81
Bed 9
122 21.94
Bed 10
121 21.76
Bed 11
0 0.00
Bed 12
0 0.00
=============================================================================
PROBLEM
No. 5
Credit:
150 Points
Your employer needs a
backend for a translator for a very SIC machine (Simplified Instruction
Computer). Input to the translator will be arithmetic expressions in postfix
form and the output will be assembly language code.
The target machine has
a single register and the following instructions, where the operand is either
an identifier or a storage location.
L load the operand into
the register
A add the operand to the
contents of the register
S subtract the operand
from the contents of the register
M multiply the contents
of the register by the operand
D divide the contents of
the register by the operand
N negate the contents of
the register
ST store the contents of
the register in the operand location
An arithmetic operation replaces the contents of the register with
the expression result. Temporary storage locations are allocated by the
assembler for an operand of the form $n where n is a single digit.
Input and Output
The input file consists of several legitimate postfix expressions,
each on a separate line. Expression
operands are single letters and operators are the normal arithmetic operators
(+, -, *, /) and unary negation (@).
Output must be assembly language code that meets the following
requirements:
1. One instruction per line with the instruction mnemonic
separated from the
operand (if any) by one
blank.
2. One blank line must separate the assembly code for successive
expressions.
3. The original order of the operands must be preserved in the
assembly code.
4. Assembly code must be generated for each operator as soon as it
is
encountered.
5. As few temporaries as possible should be used (given the
above
restrictions).
6. For each operator in the expression, the minimum number of
instructions
must be generated (given
the above restrictions).
TEST CASES:
CASE 1
Input Output
AB+CD+EF++GH+++ L A
A B
ST $1
L C
A D
ST $2
L E
A F
A $2
ST $2
L G
A H
A $2
A $1
CASE 2
Input Output
AB+CD+- A B
ST $1
L C
A D
N
A $1
=============================================================================
PROBLEM No. 6
Credit:
200 Points
You and your party of explorers have discovered an Aztec temple.
In the underground dungeon under the temple, there is an immense thick floor of
solid gold. There is also a manuscript that says something strange. You have to
walk on the gold surface holding a piece of elephant bone that was lying in the
dungeon itself. You must walk one step at a time, either North, East, West or
South. Each step must be exactly equal, and 1 unit long. The exact sequence of
North, East, West or South steps you must take is also given in the manuscript
itself.
As you take steps as specified in the manual, you are in effect
walking in a 2D grid with squares with sides of unit length. Please note that
the size of the grid is NOT specified in advance and is infinite as far as you
are concerned. (The Aztecs had plenty of gold)
We define a unit square as one having all its sides of length 1
unit.
The manuscript says that if you walk on all the four edges of a
unit square at least once, a divine pattern will appear on that unit square.
Our aim is to find the number of unit squares whose sides have
been traversed at least once. Please note that the direction of traversal is
not of concern to us, also the sides may not have been traversed in sequence.
Your program will read in a sequence of directions, specified by letters
N, E, W, or S, separated by new lines and output the number of unit squares
that have been covered with divine patterns at the end of your walk.
For example, a sample input is
N
E
S
W
W
S
N
E
S
W
On
reading this, your program should output :
2
=============================================================================