The problem statements given below were used during the past few years of the ACM North Central contest. The actual problem statements were prepared using MS Word, and the versions shown here have been presented in a text-only form for simplicity. Some small differences may therefore exist between the versions shown here and those actually presented to the contestants.
Problem 1: Mapping the Swaps Sorting an array can be done by swapping certain pairs of adjacent entries in the array. This is the fundamental technique used in the well-known bubble sort. If we list the identities of the pairs to be swapped, in the sequence they are to be swapped, we obtain what might be called a swap map. For example, suppose we wish to sort the array A whose elements are 3, 2, and 1 in that order. If the subscripts for this array are 1, 2, and 3, sorting the array can be accomplished by swapping A2 and A3, then swapping A1 and A2, and finally swapping A2 and A3. If a pair is identified in a swap map by indicating the subscript of the first element of the pair to be swapped, then this sorting process would be characterized with the swap map 2 1 2. It is instructive to note that there may be many ways in which swapping of adjacent array entries can be used to sort an array. The previous array, containing 3 2 1, could also be sorted by swapping A1 and A2, then swapping A2 and A3, and finally swapping A1 and A2 again. The swap map that describes this sorting sequence is 1 2 1. For a given array, how many different swap maps exist? A little thought will show that there are an infinite number of swap maps, since sequential swapping of an arbitrary pair of elements will not change the order of the elements. Thus the swap map 1 1 1 2 1 will also leave our array elements in ascending order. But how many swap maps of minimum size will place a given array in order? That is the question you are to answer in this problem. The input data will contain an arbitrary number of test cases, followed by a single 0. Each test case will have a integer n that gives the size of an array, and will be followed by the n integer values in the array. For each test case, print a message similar to those shown in the sample output below. In no test case will n be larger than 5. Sample Input 2 9 7 2 12 50 3 3 2 1 3 9 1 5 0 Expected Output There are 1 swap maps for input data set 1. There are 0 swap maps for input data set 2. There are 2 swap maps for input data set 3. There are 1 swap maps for input data set 4.
Problem 2: Rational Numbers from Repeating Fractions
A rational number is any which can be written in the form p/q, where p and q
are integers. All rational numbers less than 1 (that is, those for which p
is less than q) can be expanded into a decimal fraction, but this expansion
may require repetition of some number of trailing digits. For example, the
rational number 7/22 has the decimal expansion .3181818.. Note that the pair
of digits 1 and 8 repeat ad infinitum. Numbers with such repeating decimal
expansions are usually written with a horizontal bar over the repeated
__
digits, like this: .318
If we are given the decimal expansion of a rational fraction (with an
indication of which digits are repeated, if necessary), we can determine
the rational fraction (that is, the integer values of p and q in p/q) using
the following algorithm.
Assume there are k digits immediately after the decimal point that are not
repeated, followed by a group of j digits which must be repeated. Thus for
7/22 we would have k = 1 (for the digit 3) and j = 2 (for the digits 1
and 8). Now if we let X be the original number (7/22), we can compute the
numerator and denominator of the expression
10**(k+j) * X - 10**k * X
-------------------------
10**(k+j) - 10**k
__
For .318 we obtain the following calculation for the numerator of this fraction:
__ __ __ __
10**3 * .318 - 10**1 * .318 = 318.18 - 3.18 = 315
The denominator is just 1000 - 10, or 990. It is important to note that the
expression in the numerator and the denominator of this expression will always
yield integer values, and these represent the numerator and denominator of the
__
rational number. Thus the repeated fraction .318 is the decimal expansion
of the rational number 315/990. Properly reduced, this fraction is (as
expected) just 7/22.
The input data for this problem will be a sequence of test cases, each test
case appearing on a line by itself, followed by a -1. Each test case will
begin with an integer giving the value of j, one or more spaces, then
the decimal expansion of a fraction given in the form 0.ddddd (where d
represents a decimal digit). There may be as many as nine (9) digits in the
decimal expansion (that is, the value of k+j may be as large as 9). For each
test case, display the case number (they are numbered sequentially starting
with 1) and the resulting rational number in the form p/q, properly reduced.
Sample Input
2 0.318
1 0.3
2 0.09
6 0.714285
-1
Expected Output
Case 1: 7/22
Case 2: 1/3
Case 3: 1/11
Case 4: 5/7
Problem 3: Recognizing Good ISBNs
Most books now published are assigned a code which uniquely identifies the
book. The International Standard Book Number, or ISBN, is normally a
sequence of 10 decimal digits, but in some cases, the capital letter X may
also appear as the tenth digit. Hyphens are included at various places in
the ISBN to make them easier to read, but have no other significance. The
sample input and expected output shown below illustrate many valid, and a
few invalid, forms for ISBNs.
Actually, only the first nine digits in an ISBN are used to identify a book.
The tenth character serves as a check digit to verify that the preceding 9
digits are correctly formed. This check digit is selected so that the value
computed as shown in the following algorithm is evenly divisible by 11.
Since the check digit may sometimes need to be as large as 10 to guarantee
divisibility by 11, a special symbol was selected by the ISBN designers to
represent 10, and that is the role played by X.
The algorithm used to check an ISBN is relatively simple. Two sums, s1 and
s2, are computed over the digits of the ISBN, with s2 being the sum of the
partial sums in s1 after each digit of the ISBN is added to it. The ISBN
is correct if the final value of s2 is evenly divisible by 11.
An example will clarify the procedure. Consider the (correct) ISBN
0-13-162959-X (for Tanenbaum's Computer Networks). First look at the
calculation of s1:
-----------------------------------------------------------------
digits in the ISBN 0 1 3 1 6 2 9 5 9 10(X)
partial sums 0 1 4 5 11 13 22 27 36 46
-----------------------------------------------------------------
The calculation of s2 is done by computing the total of the partial sums
in the calculation of s1:
-----------------------------------------------------------------
s2 (running totals) 0 1 5 10 21 34 56 83 119 165
-----------------------------------------------------------------
We now verify the correctness of the ISBN by noting that 165 is, indeed,
evenly divisible by 11.
The input data for this problem will contain one candidate ISBN per line of
input, perhaps preceded and/or followed by additional spaces. No line will
contain more than 80 characters, but the candidate ISBN may contain illegal
characters, and more or fewer than the required 10 digits. Valid ISBNs may
include hyphens at arbitrary locations. The end of file marks the end of
the input data.
The output should include a display of the candidate ISBN and a statement
of whether it is legal or illegal. The expected output shown below
illustrates the expected form.
Sample Input
0-89237-010-6
0-8306-3637-4
0-06-017758-6
This_is_garbage
1-56884-030-6
0-8230-2571-3
0-345-31386-0
0-671-88858-7
0-8104-5687-7
0-671-74119-5
0-812-52030-0
0-345-24865-1-150
0-452-26740-4
0-13-139072-4
0-1315-2447-X
Expected Output
0-89237-010-6 is correct.
0-8306-3637-4 is correct.
0-06-017758-6 is correct.
This_is_garbage is incorrect.
1-56884-030-6 is correct.
0-8230-2571-3 is correct.
0-345-31386-0 is correct.
0-671-88858-7 is correct.
0-8104-5687-7 is correct.
0-671-74119-5 is correct.
0-812-52030-0 is correct.
0-345-24865-1-150 is incorrect.
0-452-26740-4 is correct.
0-13-139072-4 is correct.
0-1315-2447-X is correct.
Problem 4: Identifying Concurrent Events It is important in distributed computer systems to identify those events (at identifiable points in time) that are concurrent, or not related to each other in time. A group of concurrent events may sometimes attempt to simultaneously use the same resource, and this could cause problems. Events that are not concurrent can be ordered in time. For example, if event e1 can be shown to always precede event e2 in time, then e1 and e2 are obviously not concurrent. Notationally we indicate that e1 precedes e2 by writing e1->e2. Note that the precedes relation is transitive, as expected. Thus if e1->e2 and e2->e3, then we can also note that e1->e3. Sequential events in a single computation are not concurrent. For example, if a particular computation performs the operations identified by events e1, e2 and e3 in that order, then clearly and e1->e2 and e2->e3. Computations in a distributed system communicate by sending messages. If event esend corresponds to the sending of a message by one computation, and event erecv corresponds to the reception of that message by a different computation, then we can always note that esend->erecv, since a message cannot be received before it is sent. In this problem you will be supplied with lists of sequential events for an arbitrary number of computations, and the identification of an arbitrary number of messages sent between these computations. Your task is to identify those pairs of events that are concurrent. Input and Output Specifications A number of test cases will be supplied. For each test case the input will include first an integer, NC, specifying the number of computations in the test case. For each of these NC computations there will be a single line containing an integer NEi that specifies the number of sequential events in the computation followed by NEi event names. Event names will always contain one to five alphanumeric characters, and will be separated from each other by at least one blank. Following the specification of the events in the last computation there will be a line with a single integer, NM, that specifies the number of messages that are sent between computations. Finally, on each of the following NM lines there will be a pair of event names specifying the name of the event associated with the sending of a message, and the event associated with the reception of the message. These names will have previously appeared in the lists of events associated with computations, and will be separated by at least one blank. The last test case will be followed by the single integer 0 on a line by itself. For each test case, print the test case number (they are numbered sequentially starting with 1), the number of pairs of concurrent events for the test case, and any two pair of the concurrent event names. If there is only one concurrent pair of events, just print it. And if there are no concurrent events, then state that fact. Example Consider the following input data: 2 2 e1 e2 2 e3 e4 1 e3 e1 0 There are two computations. In the first e1->e2 and in the second e3->e4. A single message is sent from e3 to e1, which means e3->e1. Using the transitive property of the precedes relation we can additionally determine that e3->e2. This leaves the pairs (e1,e4) and (e2,e4) as concurrent events. Sample Input 2 2 e1 e2 2 e3 e4 1 e3 e1 3 3 one two three 2 four five 3 six seven eight 2 one four five six 1 3 x y zee 0 2 2 alpha beta 1 gamma 1 gamma beta 0 Expected Output Case 1, 2 concurrent events: (e1,e4) (e2,e4) Case 2, 10 concurrent events: (two,four) (two,five) Case 3, no concurrent events. Case 4, 1 concurrent events: (alpha,gamma)
Problem 5: Processing MX Records Mapping symbolic machine names, like bigone.stateu.edu, to the corresponding Internet network address (like 24.99.100.33) is a major function of the Domain Naming System, or DNS. The pieces of a machine's symbolic name, separated by periods, correspond to nodes in a tree when the name is read right to left. The pieces corresponding to internal nodes in the tree correspond to domains. The edu domain, for example, is the node under which we find all college and university machines in the United States. All machines in Canada are found under the ca domain. By providing one or more MX records (lines of text in a particular file), a system manager can arrange for DNS to route mail bound for one machine to another instead. Rerouting is appropriate in many cases, but one frequent use is to create addresses for fictitious machines with meaningful names. For example, it might be nice to allow mail to be addressed to info.stateu.edu, but not have a specific machine named info on the stateu campus. The mail could be redirected to bigone.stateu.edu by using an appropriate MX record. In this problem we'll deal with processing a simplified form of MX records. An MX record has three fields, or sequences of non-blank characters. These fields are separated by one or more blanks. The first field, if present, always begins in the first column on a line. If the first field is not present, then it is assumed to be the same as the first field from the preceding line (or the one assumed for that line if it didn't have one). The first and third fields are symbolic machine names, and will contain no more than 36 characters. The second field is a non-negative integer specifying a preference. Let's look at an example. info.stateu.edu 0 bigone.stateu.edu 10 tiny.stateu.edu The first line says that all mail destined for info.stateu.edu should be delivered to bigone.stateu.edu. The preference in this MX record is 0, versus 10 for the second MX record. If bigone.stateu.edu is down, then mail for info would instead be redirected to tiny. Smaller numbers indicate higher preference, and MX records need not be given in order of increasing preference. Wildcard MX records allow redirection of mail to many machines with a single MX record. For example, *.citycc.midville.edu 0 tiny.stateu.edu would redirect mail to any machine whose name has the symbolic suffix .citycc.midville.edu to the machine tiny on the stateu campus. For simplicity, we will assume that the asterisk (*) representing a wildcard record will appear only in the first part of a wildcarded symbolic name, and that no more than three periods will occur in any symbolic name. Input, Output and Processing What you will do in this problem is record MX records, process commands that indicate when machines go up or down, and process requests to determine how to redirect mail based on the recorded MX records. The input begins with a line containing an integer N, following by N lines, each of which contain an MX record that is to be read and recorded. (There is no explicit limit on the value of N.) The remaining lines of input (after the N MX records) will each begin with the letter U, D, A, or X in column 1. Following a U or D will be one or more blanks and a machine name. D means the machine is now down (not operational), while U means it is now up. All machines are initially assumed to be up at the beginning of the input. An A in column 1 will be followed by one or more spaces and a symbolic machine name. That machine name is to be processed (at the time the line is read) using the recorded MX records and the up/down status of machines to determine how mail to that machine should be directed. Of course some machines may not have their mail redirected, so be prepared to handle these cases. Output for these A lines is as shown in the samples. Note the output style for machines which have no redirection indicated (that is, there are no applicable MX records). The end of input is indicated by a line containing X in column 1. Notes 1. No input line will contain more than 80 characters. 2. MX records are not to be processed recursively. Thus if mail to first.com is being redirected to second.com by one MX record, any additional MX records that might redirect mail from second.com to another machine are not examined during the processing of first.com. Sample Input 5 service.stateu.edu 10 tiny.stateu.edu info.stateu.edu 0 bigone.stateu.edu 10 tiny.stateu.edu service.stateu.edu 5 bigone.stateu.edu *.smallu.edu 10 service.stateu.edu A alpha.cs.smallu.edu A info.stateu.edu D bigone.stateu.edu A info.stateu.edu A nowhere.com X Expected Output alpha.cs.smallu.edu => service.stateu.edu info.stateu.edu => bigone.stateu.edu info.stateu.edu => tiny.stateu.edu nowhere.com =>
Problem 6: A Node Too Far
To avoid the potential problem of network messages (packets) looping around
forever inside a network, each message includes a Time To Live (TTL) field.
This field contains the number of nodes (stations, computers, etc.) that can
retransmit the message, forwarding it along toward its destination, before the
message is unceremoniously dropped. Each time a station receives a message
it decrements the TTL field by 1. If the destination of the message is the
current station, then the TTL field's value is ignored. However, if the
message must be forwarded, and the decremented TTL field contains zero, then
the message is not forwarded.
In this problem you are given the description of a number of networks, and
for each network you are asked to determine the number of nodes that are not
reachable given an initial node and TTL field value. Consider the following
example network:
10-----15-----20-----25
| | | |
30 35-----40-----45
/ | | |
47 | | |
\ | | |
50-----55-----60-----65
If a message with a TTL field of 2 was sent from node 35 it could reach
nodes 15, 10, 55, 50, 40, 20 and 60. It could not reach nodes 30, 47, 25,
45 or 65, since the TTL field would have been set to zero on arrival of
the message at nodes 10, 20, 50 and 60. If we increase the TTL field's
initial value to 3, starting from node 35 a message could reach all except
node 45.
Input and Output Format
There will be multiple network configurations provided in the input. Each
network description starts with an integer NC specifying the number of
connections between network nodes. An NC value of zero marks the end of the
input data. Following NC there will be NC pairs of positive integers.
These pairs identify the nodes that are connected by a communication line.
There will be no more than one (direct) communication line between any pair
of nodes, and no network will contain more than 30 nodes. Following each
network configuration there will be multiple queries as to how many nodes
are not reachable given an initial node and TTL field setting. These queries
are given as a pair of integers, the first identifying the starting node
and the second giving the initial TTL field setting. The queries are
terminated by a pair of zeroes.
For each query display a single line showing the test case number (numbered
sequentially from one), the number of nodes not reachable, the starting
node number, and the initial TTL field setting. The sample input and output
shown below illustrate the input and output format.
Sample Input
16
10 15 15 20 20 25 10 30 30 47 47 50 25 45 45 65
15 35 35 55 20 40 50 55 35 40 55 60 40 60 60 65
35 2 35 3 0 0
14
1 2 2 7 1 3 3 4 3 5 5 10 5 11
4 6 7 6 7 8 7 9 8 9 8 6 6 11
1 1 1 2 3 2 3 3 0 0
0
Expected Output
Case 1: 5 nodes not reachable from node 35 with TTL = 2.
Case 2: 1 nodes not reachable from node 35 with TTL = 3.
Case 3: 8 nodes not reachable from node 1 with TTL = 1.
Case 4: 5 nodes not reachable from node 1 with TTL = 2.
Case 5: 3 nodes not reachable from node 3 with TTL = 2.
Case 6: 1 nodes not reachable from node 3 with TTL = 3.
Problem 7: Interpreting Control Sequences
Virtually all text-mode terminals are special-purpose computer systems,
including a serial port (for communication with a modem or another computer
system), a keyboard, a CRT, and of course, a microprocessor, some RAM, and a
control program in ROM.
When a character arrives at the terminal, either from the keyboard or the
serial port, the terminal's software classifies it as either a display
character (which is to be displayed on the CRT) or as a character that
introduces a control sequence. A control sequence is used to direct the
terminal to do such things as clear the screen, move the cursor in a specified
manner, or perhaps change fonts.
In this problem assume you are writing the software for a small terminal with
a 10-row, 10-column display (perhaps for a point-of-sale terminal). Rows and
columns are numbered 0 through 9. The character that introduces a control
sequence is ^, the circumflex. The character (or in one case, the two
characters) immediately following the control sequence introducer will direct
your software in performing its special functions. Here is the complete
list of control sequences you will need to interpret:
^b Move the cursor to the beginning of the current line; the cursor row
does not change
^c Clear the entire screen; the cursor row and column do not change
^d Move the cursor down one row if possible; the cursor column does not change
^e Erase characters to the right of, and including, the cursor column on
the cursor's row; the cursor row and column do not change
^h Move the cursor to row 0, column 0; the image on the screen is not changed
^i Enter insert mode (see below)
^l Move the cursor left one column, if possible; the cursor row does
not change
^o Enter overwrite mode (see below)
^r Move the cursor right one column, if possible; the cursor row does
not change
^u Move the cursor up one row, if possible; the cursor column does not change
^^ Write a circumflex (^) at the current cursor location, exactly as if it
was not a special character; this is subject to the actions of the current
mode (insert or overwrite)
^## Move the cursor to the row and column specified; # represents a decimal
digit; the first # represents the new row number, and the second #
represents the new column number
No illegal control sequences will ever be sent to the terminal. The cursor
cannot move outside the allowed screen locations (that is, between row 0,
column 0 and row 9, column 9).
When a normal character (not part of a control sequence) arrives at the
terminal, it is displayed on the terminal screen in a manner that depends on
the terminal mode. When the terminal is in overwrite mode (as it is when it
is first turned on), the received character replaces the character at the
cursor's location. But when the terminal is in insert mode, the characters
to the right of and including the cursor's location are shifted right one
column, and the new character is placed at the cursor's location; the
character previously in the rightmost column of the cursor's row is lost.
Regardless of the mode, the cursor is moved right one column, if possible.
Input Data
The input will contain multiple tests of your terminal software. Each test
begins with a line containing an integer N. Following this line there will
be N more lines of data, each character of which is to be treated as
if it was input, in the order read, to your terminal software. There will be
no tab characters in the input data, and ends of lines in the input are to be
ignored. Note that blanks in the input data are normal characters to
be displayed on your terminal's screen. The last test will be followed by a
single line containing the integer 0. No control sequence will be split
between two lines of the input data.
At the beginning of each test case you are to assume the terminal screen is
clear (that is, filled with blanks), that the terminal is in overwrite mode,
and that the cursor is in row 0, column 0 of the screen.
Output Format
For each input test case, output a line with the case number (these are
numbered sequentially starting with 1) and the screen image the way it would
look at the end of processing the data in the test case. Enclose the
screen image in a "box;" see the sample below for illustration of the required
format.
Sample Input WITH BLANKS SHOWN AS HYPHENS FOR CLARITY
7
This-is-bad^h^c
^05^^
^14/-\^d^b---/---\
^u^d^d^l^l^l^l^l^l^l^l^l
^r^r<-ACM->^l^l^d/^b---\
^b^d----\-/
^d^l^lv
7
^i9^l8^l7^l6^l5^l4^l3^l2^l1^l0
^o^d^lThis-is-#1^d^bThis-is-#2
^d^bThis-is-#3^d^bThis-is-#4
^d^bThis-is-#5^d^bThis-is-#6
^d^bThis-is-#7^d^bThis-is-#8
^i^d^bThis-is-#9^d^bThis-is-#10
^54^e-Hello^d^l^l^l^lWorld
0
Expected Output
Case 1
+----------+
| ^ |
| / \ |
| / \ |
| < ACM > |
| \ / |
| \ / |
| v |
| |
| |
| |
+----------+
Case 2
+----------+
|0123456789|
|This is #1|
|This is #2|
|This is #3|
|This is #4|
|This Hello|
|This World|
|This is #7|
|This is #8|
|This is #0|
+----------+
Problem A
Factorial Frequencies
In an attempt to bolster her sagging palm-reading business,
Madam Phoenix has decided to offer several numerological treats to
her customers. She has been able to convince them that the
frequency of occurrence of the digits in the decimal representation of
factorials bear witness to their futures. Unlike palm-reading, how-
ever, she can't just conjure up these frequencies, so she has
employed you to detemine these values.
Recall that the definition of n! (that is, n factorial) is just 1 x 2
x 3 x ... x n. As she expects to use either the day of the week, the day of
the month, or the day of the year as the value of n, you must
be able to determine the number of occurrences of each decimal digit
in numbers as large as 366 factorial (366!), which has 781 digits.
The input data for the program is simply a list of integers for
which the digit counts are desired. All of these input values will
be less than or equal to 366 and greater than 0, except for the last
integer, which will be zero. Don't bother to process this zero value;
just stop your program at that point. The output fomat isn't too
critical, but you should make your program produce results that
look similar to those shown below.
Madam Phoenix will be forever (or longer) in your debt; she might
even give you a trip if you do your job well!
Sample Input
3
8
100
0
Expected Output
3! --
(0) 0 (1) 0 (2) 0 (3) 0 (4) 0
(5) 0 (6) 1 (7) 0 (8) 0 (9) 0
8! --
(0) 2 (1) 0 (2) 1 (3) 1 (4) 1
(5) 0 (6) 0 (7) 0 (8) 0 (9) 0
100! --
(0) 30 (1) 15 (2) 19 (3) 10 (4) 10
(5) 14 (6) 19 (7) 7 (8) 14 (9) 20
(The formatting of the "Expected Output" was munged somewhat; all lines
should have the same horizontal spacing.)
Problem B
Identifying Legal Pascal Real Constants
Pascal requires that real constants have either a decimal point, or an
exponent (starting with the letter e or E, and officially called a scale
factor), or both, in addition to the usual collection of decimal digits.
If a decimal point is included it must have at least one decimal digit on
each side of it. As expected, a sign (+ or -) may precede the entire
number, or the exponent, or both. Exponents may not include frac-
tional digits. Blanks may precede or follow the real constant, but they
may not be embedded within it. Note that the Pascal syntax rules for
real constants make no assumptions about the range of real values, and
neither does this problem.
Your task in this problem is to identify legal Pascal real constants.
Each line of the input data contains a candidate which you are to classify.
For each line of the input, display your finding as illustrated in the
example shown below. The input terminates with a line that contains only
an asterisk in column one.
Example Input Expected Output
1.2 1.2 is legal.
1. 1. is illegal.
1.0e-55 1.0e-55 is legal.
e-12 e-12 is illegal.
6.5E 6.5E is illegal.
le-12 le-12 is legal.
+4.1234567890E-99999 +4.1234567890E-99999 is legal.
7.6e+12.5 7.6e+12.5 is illegal.
99 99 is illegal.
*
Problem C
Extrapolation Using a Difference Table
A very old technique for extrapolating a sequence of values is based
on the use of a difference table. The difference table used in the
extrapolation of a sequence of 4 values, say 3, 6, 10, and 15,
might be displayed as follows:
3
3
6 1
4 0
10 1
5
15
The original sequence of values appears in the first column of the
table. Each entry in the second column of the table is formed by com-
puting the difference between the adjacent entries in the first column.
These values (in the second column) are called first differences. Each
entry in the third column is similarly the difference between the adja-
cent entries in the second column; the third column entries are naturally
called second differences. Computation of the last column in this
example should now be obvious (but beware that this value is not
always zero). Note that the last column will always contain only a single
value. If we begin with a sequence of n values, the completed difference
table will have n columns, with the single value in column n
representing the single n-1st difference.
To extrapolate using a difference table we assume the n-1st differ-
ences are constant (since we have no additional informafion to refute
that assumption). Given that assumption, we can compute the next
entry in the n-2nd difference column, the n-3rd difference column, and so
forth until we compute the next entry in the first column which, of
course, is the next value in the sequence. The table below shows the
four additional entries (in boxes) added to the table to compute the next
entry in the example sequence, which in this case is 21. We could
obviously continue this extraolation process as far as desired by
adding additional entries to the columns using the assumption that the n-
1st differences are constant.
3
3
6 1
4 0
10 1
5 0
15 1
6
21
The input for this problem will be a set of extraolation requests.
For each request the input will contain first an integer n, which
specifies the number of values in the sequence to be extended. When n
is zero your program should terminate. If n is non-zero (it will never be
larger than 10), it will be followed by n integers representing the
given elements in the sequence. The last item in the input for each
extrapolation request is k, the number of extrapolation operations to per-
form; it will always be at least 1. In effect, you are to add k entries
to each column of the difference table, finally reporting the last value of
the sequence computed by such extrapolation. More precisely, assume the
first n entries (the given values) in the sequence are numbered 1
through n. Your program is to determine the n+kth value in the
sequence by extrapolation of the original sequence k times. (Hint: no
upper limit is given for k, and you might not be able to acquire
enough memory to construct a complete difference table.)
Example Input Expected Output
4 3 6 10 15 1 Term 5 of the sequence is 21
4 3 6 10 15 2 Term 6 of the sequence is 28
3 2 4 6 20 Term 23 of the sequence is 46
6 3 9 12 5 18 -4 10 Term 16 of the sequence is -319268
0
Problem D
Evaluating Simple C Expressions
The task in this problem is to evaluate a sequence of simple C
expressions, buy you need not know C to solve the problem! Each of
the expressions will appear on a line by itself and will contain no more
than 80 characters. The expressions to be evaluated will contain only
simple integer variables and a limited set of operators; there will be
no constants in the expressions. There are 26 variables which may
appear in our simple expressions, namely those with the names a through
z (lower-case letters only). At the beginning of evaluation of each
expression, these 26 variables will have the integer values 1 through 26,
respectively (that is, a = 1, b = 2, ...). Each variable will appear at
most once in an expression, and many variables may not be used at
all.
The operators that may appear in expressions include the b@
(two-operand) + and -, with the usual interpretation. Thus the
expression a + c - d + b has the value 2 (computed as I +
3 - 4 + 2). The only other operators that may appear in expressions
are + + and - -. These are unary (one- operand) operators, and may
appear before or after any variable. When the ++ operator appears
before a variable, that variable's value is incremented (by one) before
the variable's value is used in determining the value of the entire
expression. Thus the value of the expression ++ c - b is 2,
with c being incremented to 4 prior to evaluating the entire expression.
When the ++ operator appears after a variable, that variable is incre-
mented (again, by one) after its value is used to determine the value
of the entire expression. Thus the value of the expression c ++
- b is 1, but c is incremented after the complete expression is
evaluated,; its value will still be 4. The -- operator can also be used
before or after a variable to decrement (by one) the variable; its place-
ment before or after the variable has the same signficance as for
the ++ operator. Thus the expression -- c + b -- has
the value 4, with variables c and b having the values 2 and I follwing
the evaluation of the expression.
Here's another, more algorithmic, approach to explaining the ++
and -- operators. We'll consider only the ++ operator, for brevity:
1. Identify each variable that has a ++ operator before it. Write a
simple assignment statement that increments the value of each such
variable, and remove the ++ operator from before that variable
in the expression.
2. In a similar manner, identify each variable that has a ++ operator
after it. Write a simple assignment statement that increments the
value of each of these, and remove the ++ operator from
after that variable in the expression.
3. Now the expression has no ++ operators before or after any
variables. Write the statement that evaluates the remaining
expression after those statements written in step 1, and before
those written in step 2.
4. Execute the statements generated in step 1, then those generated
in step 3, and finally the one generated in step 2, in that
order.
Using this approach, evaluating the expression ++ a + b ++ is
equivalent to computing
a = a + 1 (from step 1 of the algorithm)
expression = a + b (from step 3)
b = b + 1 (from step 2)
where expression would receive the value of the complete expression.
Your program is to read expressions, one per line, until a totally
blank (or empty) line is read. Display each expression exactly as it
was read, then display the value of the entire expression, and on
separate lines, the value of each variable after the expression was
evaluated. Do not display the value of variables that were not used in
the expression. The samples shown below illustrate the desired output for-
mat.
Blanks are to be ignored in evaluating expressions, and you are
assured that ambiguous expressions like a+++b (ambiguous because it could
be treated as a++ + b or a + ++b) will not appear in the input. Like-
wise, ++ or -- operators will never appear both before and after a single
variable. Thus expressions like ++a++ will not be in the input data.
Sample Input Expected Output
a + b Expression: a + b
b - z value = 3
a+b--+c++ a = 1
c+f--+--a b = 2
f-- + c-- + d-++e Expression: b - z
(This line is blank!) value = -24
b = 2
z = 26
Expression: a+b--+c++
value = 6
a = 1
b = 1
c = 4
Expression: c+f--+--a
value = 9
a = 0
c = 3
f = 5
Expression: f-- + c-- + d-++e
value = 7
c = 2
d = 4
e = 6
f = 5
Problem E
The Finite State Text Processing Machine
A finite state machine (FSM) is essentially a directed graph. Each
node in the graph is called a state; at any point during execution of
the FSM, one of the states is said to be the current state. Each directed
edge between two states is called a transition. When the conditions are
right, one of the transitions from the current state is said to occur,
and the current state changes to a new state as determined by the transi-
tion. Consider the following very simple example.
+----------1---------+
| | +--------+
| v | |
+---+ +---+ |
| A | | B | 3
+---+ +---+ |
^ | ^ |
| | | |
+----------2---------+ +--------+
There are two states in this FSM, labelled A and B, and three transitions,
labelled 1, 2 and 3. If the current state is A, and the conditions
for transition 1 are met, then the current state becomes B. When the
current state is B, and the conditions for transition 2 are met, the
current state becomes A again. If the current state is B and the condi-
tions for transition 3 are met, the current state remains B.
In this problem the input will be descriptions of several FSMs.
Each transition in these FSMs has an associated set of characters
called the input set, and a string called the output string. A transi-
tion can occur when the current input data character is in the
transition's input set. When the transition occurs, the output string is
printed.
Input Description
The input consists of a sequence of pairs (FSM description, input
for the FSM). A FSM is described by the following sequence of items
separated by whitespace (blanks, tabs, and end of line characters):
* An integer specifying the number of states in the FSM. For each of
these states there will be the following items, in order:
* A one to eight character name for the state. State names are
case significant, and unique.
* An integer specifying the number of transitions that leave the
current state. For each of these transitions there will be
the following data items, in order:
* The set of input characters that enable the transition (see
below).
* The name of the new current state when this transition
occurs.
* The output string (see below).
The input set and the output string are given as sequences of
printable characters with no embedded whitespace. Several special con-
structions may appear in these, however. When \b appears it is to
be interpreted as a blank. Treat \n as an end of line, and \\ as a single
backslash. The construcfion \0 (that is, backslash followed by zero) will
appear only as an output string, and means to print nothing when the
transition occurs. The construction \c appearing as an input set matches
anything. That is, if none of the other transitions are enabled and a
transition has \c specified as its input set, then it is enabled. When \c
appears in an output string, it means to print the current input character.
This could appear several times in the same output string.
After the last item in the description of a FSM has been read
begin "executing" the FSM using the characters that start on the first
complete line following the description. The beginning state will
always be called START. The final state will always be called END,
but will not appear as a state in the description of a FSM. All
input is guaranteed to be correct.
Output Description and Examples
For each input your program should display the FSM number (1, 2, ...)
and, beginning on the next line, the output that results from those transi-
tions that occur. The examples below illustrate this.
The first example FSM replaces each vowel in a single line of input
with an asterisk. The second example will delete each vowel that follows a
lower or upper case X, again processing only a single line of input. The
final example changes the case of each odd-numbered vowel in the input;
processing stops when an exclamation point is encountered, and the
remainder of the input line is ignored.
Input Data Expected Output
1 Finite State Machine 1:
START 3 Th*s *s *np*t f*r *x*mpl* *n*.
AEIOUaeiou START Finite State Machine 2:
\n END \n XXx Test Xo iXx
\c START \c Finite State Machine 3:
This is input for example one. ThIs is sOme dAta fOr FSM numbEr 3.
2
START 3
\c START \c
Xx SKIP \c
\n END \n
SKIP 4
AEIOU START \0
aeiou START \0
Xx SKIP \c
\n END \n
XaXxe Test XIo iXixo
3
START 12
\c START \c ! FINIS \0
A TWO a E TWO e
I TWO i 0 TWO o
U TWO u a TWO A
e TWO E i TWO I
o TWO 0 u TWO U
TWO 4
\c TWO \c AEIOU START \c
aeiou START \c ! FINIS \0
FINIS 2
\c FINIS \0 \n END \n
This is some data for FSM number 3.
! IGNORED.
0
Problem F
PostScript Emulation
PostScript(R) is widely used as a page description language
for laser printers. The basic unit of measurement in PostScript is
the point, and there are assumed to be exactly 72 points per inch.
The default coordinate system used at the beginning of a PostScript program
is the familiar Cartesian system, with the origin (the point with x and
y coordinates both equal to zero) at the lower left comer of the page.
In this problem you are required to recognize a small part of the
PostScript language. Specifically, the commands listed below must be
recognized. All commands will be given in lower-case letters. When
the word number appears in the command description, a floating point
value, with an optional sign and decimal point will be present in the
input data. When two numbers appear in a command, the first refers
to the x coordinate, and the second to the y coordinate. For simplicity,
each command will appear on a line by itself, and a single blank will
separate each component of the command. The end of line character will
immediately follow each command, and a line with a single asterisk in
column one will terminate the input.
number rotate
number represents the measure of an angle. This command rotates
the coordinate system that many degrees counterclockwise about the
current origin. This does not affect any lines that have already
been drawn on the page. Example: 90 rotate will rotate the
axes 90 degrees counterclockwise, so the positive y axis now
points to the left, and the positive x axis points up.
number number translate
Moves the origin of the coordinate system to the position specified.
The values are interpreted relative to the current origin.
Example: 612 792 translate would move the origin of the coor-
dinate system to the upper right comer of the page. Now only points
with negative x and y components will correspond to points on the
physical page (assuming an 8.5" by 11" page in the "portrait"
orientation).
number number scale
This command applies the scaling factors given to the x and y coordi-
nates. In effect, the actual x and y sizes of objects are multi-
plied by the respective scale factors. Example: 3 2 scale would
cause a line drawn from (0,0) to (72,72) to appear as if it was drawn
from the lower left comer of the page to a point three inches to the
right of the left edge of the paper and two inches up from the bot-
tom edge of the paper, assuming the original coordinate system was
in effect just before the command.
number number moveto
The current point is moved to the coordinates specified.
Example: 72 144 moveto would move the current point to one inch
from the left edge of the paper, and two inches up from the bot-
tom edge, assuming the original coordinate system was in effect.
number number rmoveto
This command is like moveto, except the numbers specified give
the coordinates of the new current point relafive to the
current position. Example: 144 -36 rmoveto would move the
current point set by the previous example two inches further to the
right and one-half inch lower on the page. Thus the coordinates of
the current point become (216,108). Notice that numbers can be
negative!
number number linoto
Draws a line from the current position to the position specified
by the numbers. The current position becomes the position
specified in the command. Example: 216 144 lineto would
draw a line from the current position to the point (216,144), and
leave the current point there. If we assume the current position from
the previous example, this would be a line from (216,108) to
(216,144), or a half-inch vertical line.
number number rlineto
This is similar to lineto, but the coordinates given in the command
are relative to the current position. Again, the end of the line
that is drawn becomes the new current position. Example: 0 144
rlineto will draw a two inch horizontal line from the current
position two inches to the right. Using the current position left
in the previous example, this draws a line from (216,144) to
(216,288), and leaves the current point at (216,288).
Your task is to read one of these small PostScript programs and to
display a program that will produce the same effect without using
the rotate, translate or scale commands. That is, each
moveto, rmoveto, lineto, and rlineto command in the original
(input) program should appear in your output (most likely with
modified numbers), but the rotate, translate and scale commands in
the input must not appear in the output. Assume the original coordinate
system is in effect at the beginning of execution. The numbers used with
the commands in the program you produce must be accurate to at
least two fractional digits.
Example Input Expected Output
300 300 moveto 300 300 moveto
0 72 rlineto 0 72 rlineto
2 1 scale 72 0 rlineto
36 0 rlineto 0 -72 rlineto
1 -4 scale 300 300 moveto
0 18 rlineto -72 0 rlineto
1 -0.25 scale 0 72 rlineto
0.5 1 scale 72 0 rlineto
300 300 translate
90 rotate
0 0 moveto
0 72 rlineto
2 1 scale
36 0 rlineto
1 -4 scale
0 18 rlineto
The figure drawn by these commands is
illustrated below. Each of the lines is
exactly one inch long.
+---------+---------+
| | |
| | |
| | |
| | |
+---------+ +
\
\
This point is at (300,300); the "\"s are not part of
the figure.
Problem G
Inventory Maintenance
Madam Phoenix (from Problem A) hasn't been too successful with
her new numerology business, so she's moving to the southwest to open
a "Fun In The Sun" store selling sunglasses, sunscreen, and other
such items. Even though she didn't make a profit using your last pro-
gram, she's decided to employ you again to write an inventory program
for her new store. Here's how it will work.
Each "activity" your program is to process will appear as a separate
line in the input file. The end of the input is marked by a line
containing an asterisk in column one; no other activity lines will be
so marked. Acfivity lines begin with a lower-case keyword identifying
the action to be performed. The names of the items in her inventory
are case sensitive, and each contains no no more than ten non-blank
characters. All fields in the activity lines are separated by blanks, and
Madam Phoenix guarantees you that there will be no errors in the
input. Here are the various types of acfivity lines your program is to
process.
new item-name item-cost item-selling-price
This line adds a new item (not previously carried in the store)
to the potential inventory. The item-cost and item-selling-
price are given as normal dollar amounts, without
the dollar sign. That is, they will contain one or more decimal
digits, a decimal point, and two more decimal digits. Note that
this activity line doesn't actually result in a change in the inven-
tory, but is used in anticipation of adding units of the new item
to the store's offerings. item-cost is what Madam Phoenix pays
for each unit of the item, and item-selling-price is the
price for which she sells the item. There will be no more than
100 total item-names ever included in the list of items. item-
cost and item-selling-price will never be larger than 100.00.
delete item-name
If an item isn't selling well, Madam Phoenix can remove it from
the inventory by including this line in the program input. All
units of item-name in the inventory are written off as a loss.
buy item-name quantity
When Madam Phoenix buys some units (at the unit-cost, previ-
ously indicated) of an item- name to offer for sale, she'll
indicate that with one of these lines in the pregrain input.
quantity indicates the number of units she purchased. The
quantity she purchases will never be larger than 5000 at a time,
but the number of units in the inventory may be as large as
10,000.
sell item-name quantity
When one or more units of an item are sold, that fact is recorded by
placing one of these lines in the input. quantity indicates
the number of units sold (at the item-selling-price pre-
viously indicated). Obviously, the quantity sold cannot exceed
the number of items in stock.
report
This line in the input requests a report. This is the only input line
for which output is expected. Your program will display
columns, with suitable headings, showing item-name, the
buying price, the selling price, the number of units in the inventory,
and the value of the units in the inventory (that is, the pro-
duct of the number of units in the inventory and the buying
price). The lines in the report should be sorted in alphabetical
order on item name. Following the last item the total value of
all units in the inventory should be displayed. Then finally, a line
should appear showing the total profit since the last report was
issued. Profit is defined as total sales, less the cost of the
items sold, less the cost of items written off (by the delete
activity). The sample output shown illustrates the desired for-
mat for the report. All numbers in the report must naturally
be exact.
Sample Input
new ShadeO1 0.50 3.79
new Towel01 1.47 6.98
new ShadeO2 0.63 4.29
new BluBlock 1.00 4.98
buy BluBlock 100
sell BluBlock 2
buy Towel01 500
buy ShadeO1 100
buy ShadeO2 100
sell Towel01 1
sell Towel01 1
sell BluBlock 2
report
delete Shade01
sell BluBlock 5
new ShadeO3 0.51 1.98
buy ShadeO3 250
sell Towel01 5
sell ShadeO3 4
sell ShadeO2 10
report
Expected Output
INVENTORY REPORT
Item Name Buy At Sell At on Hand Value
--------- ------ ------- ------- -----
BluBlock 1.00 4.98 96 96.00
Shade01 0.50 3.79 100 50.00
ShadeO2 0.63 4.29 100 63.00
Towel01 1.47 6.98 498 732.06
------------------------
Total value of inventory 941.06
Profit since last report 26.94
INVENTORY REPORT
Item Name Buy At Sell At On Hand Value
--------- ------ ------- ------- -----
BluBlock 1.00 4.98 91 91.00
ShadeO2 0.63 4.29 90 56.70
ShadeO3 0.51 1.98 246 125.46
Towel0l 1.47 6.98 493 724.71
------------------------
Total value of inventory 997.87
Profit since last report 39.93