PROBLEM 1: Following Orders
Given a list of variable constraints of the form x < y, you are to
write a program that prints all orderings of the variables that are
consistent with the constraints.
For example, given the constraints x < y and x < z there are two
orderings of the variables x, y, and z that are consistent with
these constraints: x y z and x z y.
The Input
The input consists of a sequence of constraint specifications. A
specification consists of two lines: a list of variables on one
line followed by a list of contraints on the next line. A
constraint is given by a pair of variables, where x y indicates that
x < y.
All variables are single character, lower-case letters. There
will be at least two variables, and no more than 20 variables in a
specification. There will be at least one constraint, and no more
than 50 constraints in a specification. There will be at least one,
and no more than 300 orderings consistent with the contraints in a
specification.
Input is terminated by end-of-file.
The Output
For each constraint specification, all orderings consistent with
the constraints should be printed. Orderings are printed in
lexicographical (alphabetical) order, one per line. Characters on a
line are separated by whitespace.
Output for different constraint specifications is separated by a
blank line.
Sample Input
a b f g
a b b f
v w x y z
v y x v z v w v
Sample Output
abfg
abgf
agbf
gabf
wxzvy
wzxvy
xwzvy
xzwvy
zwxvy
zxwvy
PROBLEM 2: Numbering Paths
Given the intersections connected by one-way streets in a city, you
are to write a program that determines the number of different
routes between each intersection. A route is a sequence of one-way
streets connecting two intersections.
Intersections are identified by non-negative integers. A one-way
street is specified by a pair of intersections. For example,
j k indicates that there is a one-way street from intersection j
to intersection k. Note that two-way streets can be modeled by
specifying two one-way streets: j k and kj.
Consider a city of four intersections connected by the following
one-way streets:
0 1
0 2
1 2
2 3
There is one route from intersection 0 to 1, two routes from 0 to 2
(the routes are 0->1->2 and 0->2), one route from 2 to 3, and no
other routes.
It is possible for an infinite number of different routes to
exist. For example if the intersections above are augmented by the
street 3 2, there is still only one route from 0 to 1, but there
are infinitely many different routes from 0 to 2. This is because
the street from 2 to 3 and back to 2 can be repeated yielding a
different sequence of streets and hence a different route. Thus the
route 0->2->3->2-> 3->2 is a different route than 0->2->3->2.
The Input
The input is a sequence of city specifications. Each specification
begins with the number of one-way streets in the city followed
by that many one-way streets given as pairs of intersections.
Each pair j k represents a one-way street from intersection j
to intersection k. In all cities, intersections are numbered
sequentially from 0 to the ``largest'' intersection. All integers
in the input are separated by whitespace. The input is terminated
by end-of-file.
There will never be a one-way street from an intersection to
itself. No city will have more than 30 intersections.
The Output
For each city specification, a square matrix of the number of
different routes from intersection j to intersection k is printed.
If the matrix is denoted M, then M[j][k] is the number of different
routes from intersection j to intersection k. The matrix M should
be printed in row-major order, one row per line. Each matrix
should be preceded by the string ``matrix for city k'' (with k
appropriately instantiated, beginning with 0).
If there are an infinite number of different paths between two
intersections a -1 should be printed. DO NOT worry about justifying
and aligning the output of each matrix. All entries in a row should
be separated by whitespace.
Sample Input
7
0 1 0 2 0 4 2 4 2 3 3 1 4 3
5
0 2 0 1 1 5 2 5 2 1
9
0 1 0 2 0 3 0 4 1 4 2 1 2 0 3 0 3 1
Sample Output
matrix for city 0
0 4 1 3 2
0 0 0 0 0
0 2 0 2 1
0 1 0 0 0
0 1 0 1 0
matrix for city 1
0 2 1 0 0 3
0 0 0 0 0 1
0 1 0 0 0 2
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
matrix for city 2
-1 -1 -1 -1 -1
0 0 0 0 1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
0 0 0 0 0
PROBLEM 3: Job Processing
A factory is running a production line. Two operations have to be performed on
each job: first operation "A", then operation "B". There is a certain
number of machines capable of performing each operation. Following figure shows
the organisation of the production lines.
---------------------------------------------------------------------------
_____________________
Content of the input container |*|*|*| | | | | | | |
~~~~~~~~~~~~~~~~~~~~~
________________
Type "A" machines | A1 | A2 | A3 |
~~~~~~~~~~~~~~~~
_____________________
Content of the intermediate container |*|*| | | | | | | | |
~~~~~~~~~~~~~~~~~~~~~
__________________________
Type "B" machines | B1 | B2 | B3 | B4 | B5 |
~~~~~~~~~~~~~~~~~~~~~~~~~~
_____________________
Content of the output container |*|*|*|*|*| | | | | |
~~~~~~~~~~~~~~~~~~~~~
---------------------------------------------------------------------------
A type "A" machine takes a job from the input container, performs operation
"A" and puts the job into the intermediate container. A type "B" machine takes
a job from the intermediate container, performs operation "B" and puts the job
into the output container. All machines can work in parallel and
independently of each other, and the size of each container is unlimited. The
machines have different performance characteristics, a given machine
works with a given processing time.
Give the earliest time operation "A" can be completed for all N jobs provided
that the jobs are available at time 0. (Subtask A). Also compute the
minimal amount of time that is necessary to perform both operations on N jobs
(Subtask B).
Input Data
The file INPUT.TXT contains positive integers in five lines. The first line
contains N, the number of jobs (1<=N<=1000). On the second line, the
number M1 of type "A" machines (1<=M1<=30) is given. In the third line there
are M1 integers, the job processing times of each type "A" machine.
The fourth and the fifth line contain the number M2 of type "B" machines
(1<=M2<=30) and the job processing times of each type "B" machine,
respectively. The job processing time is measured in units of time, which
includes the time needed for taking a job from a container before
processing and putting it into a container after processing. Each processing
time is at least 1 and at most 20.
Output Data
Your program should write two lines to file OUTPUT.TXT. The first line should
contain one positive integer: the solution of subtask A. The second line
should contain the solution of subtask B.
Example Input and Output
INPUT
5
2
1 1
3
3 1 4
OUTPUT
3
5
PROBLEM 4: Network of Schools
A number of schools are connected to a computer network. Agreements have been
developed among those schools: each school maintains a list of
schools to which it distributes software (the "receiving schools"). Note that
if B is in the distribution list of school A, then A does not necessarily
appear in the list of school B
You are to write a program that computes the minimal number of schools that
must receive a copy of the new software in order for the software to
reach all schools in the network according to the agreement (Subtask A). As a
further task, we want to ensure that by sending the copy of new
software to an arbitrary school, this software will reach all schools in the
network. To achieve this goal we may have to extend the lists of receivers
by new members. Compute the minimal number of extensions that have to be made
so that whatever school we send the new software to, it will
reach all other schools (Subtask B). One extension means introducing one new
member into the list of receivers of one school.
Input Data
The first line of file INPUT.TXT contains an integer N: the number of schools
in the network (2<=N<=100). The schools are identified by the first N
positive integers. Each of the next N lines describes a list of receivers. The
line i+1 contains the identifiers of the receivers of school i. Each list
ends with a 0. An empty list contains a 0 alone in the line.
Output Data
Your program should write two lines to the file OUTPUT.TXT. The first line
should contain one positive integer: the solution of subtask A. The second
line should contain the solution of subtask B.
Example Input and Output
INPUT
5
2 4 3 0
4 5 0
0
0
1 0
OUTPUT
1
2
(
geocities.com/ietk_csjmu)