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