Question Set 8
1. Sorting a Three-Valued Sequence - 2. Longest Prefix
Sorting is one of the most frequently done
computational tasks. Consider the special sorting problem, where
the records to be sorted have at most three different key
values. This happens for instance when we sort medalists of a
competition according to medal value, that is, gold medalists
come first, followed by silver , and bronze medalists come last.
In this task the possible key values are the
integers 1, 2 and 3. The required sorting order is
non-decreasing. Sorting has to be accomplished by a sequence of
exchange operations. An exchange operation, defined by two
position numbers p and q, exchanges the elements in positions p
and q.
You are given a sequence of key values. Write
a program that computes the minimal number of exchange operations
that are necessary to make the sequence sorted. (Subtask A).
Moreover, construct a sequence of exchange operations for the
respective sorting (Subtask B).
The first line of file INPUT.TXT
contains the number of records N (1<=N<=1000). Each of the
following N lines contains a key value.
Write on the first line of file OUTPUT.TXT
the minimal number L of exchange operations needed to make the
sequence sorted (Subtask A). The following L lines give the
respective sequence of the exchange operations in the order
performed. Each line contains one exchange operation described by
two numbers p and q, the positions of the two elements to be
exchanged (Subtask B). Positions are denoted by the numbers from
1 to N.
Figure 1 gives an input file and a
corresponding output file.
INPUT.TXT OUTPUT.TXT
9 4
2 1 3
2 4 7
1 9 2
3 5 9
3
3
2
3
1
Figure 1
The structure of some biological objects is
represented by the sequence of their constituents. These
constituents are denoted by uppercase letters. Biologists are
interested in decomposing a long sequence into shorter ones.
These short sequences are called primitives. We say that a
sequence S can be composed from a given set of primitives P, if
there are n primitives p1,...,pn in P such that the concatenation
p1...pn of the primitives equals S. By the concatenation of
primitives p1,...,pn we mean putting them together in that order
without blanks. The same primitive can occur more than once in
the concatenation and not necessarily all primitives are present.
For instance the sequence ABABACABAAB can be composed
from the set of primitives
{A, AB, BA, CA, BBC}.
The first K characters of S are the prefix of
S with length K. Write a program which accepts as input a set of
primitives P and a sequence of constituents T. The program must
compute the length of the longest prefix, that can be composed
from primitives in P.
The input data appear in two files. The file INPUT.TXT
describes the set of primitives P, while the file DATA.TXT
contains the sequence T to be examined. The first line of INPUT.TXT
contains N, the number of primitives in P (1<=N<=100). Each
primitive is given in two consecutive lines. The first line
contains the length L of the primitive (1<=L<=20). In the
second line there is a string of uppercase letters (from 'A' to
'Z') of length L. The N primitives are all different.
Each line of the file DATA.TXT
contains one uppercase letter in the first position. This file
ends with a line containing a single period ('.').
The length of the sequence is at least 1 and
at most 500,000.
Write into the first line of file OUTPUT.TXT
the length of the longest prefix of T that can be composed from
the set P.
Figure 2 gives two input files and a
corresponding output file.
INPUT.TXT DATA.TXT OUTPUT.TXT
5 A 11
1 B
A A
2 B
AB A
3 C
BBC A
2 B
CA A
2 A
BA B
C
B
.
Figure 2