Question Set 10

1. Network of Schools - 2. Magic Squares

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

Figure 1 gives a possible input file and the corresponding output file.


INPUT.TXT

5
2 4 3 0
4 5 0
0
0
1 0

OUTPUT.TXT

1
2

Figure 1

Magic Squares

Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares (see Figure 3).

1 2 3 4
8 7 6 5

Figure 3: Initial configuration

In this task we consider the version where each square has a different colour. Colours are denoted by the first 8 positive integers (see Figure 3). A sheet configuration is given by the sequence of colours obtained by reading the colours of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration.

Three basic transformations, identified by the letters 'A', 'B' and 'C', can be applied to a sheet:

All configurations are available using the three basic transformations.

A:
1 2 3 4
8 7 6 5
1 2 3 4
8 7 6 5
B:
1 2 3 4
4 1 2 3
5 8 7 6
8 7 6 5
C:
1 2 3 4
1 7 2 4
8 6 3 5
8 7 6 5

Figure 4: Basic transformations

The effects of the basic transformations are described in Figure 4. Numbers outside the squares denote square positions. If a square in position p contains number i, it means that after applying the transformation, the square whose position was i before the transformation moves to position p.

You are to write a program that computes a sequence of basic transformations that transforms the initial configuration of Figure 3 to a specific target configuration (Subtask A). Two extra points will be given for the solution if the length of the transformation sequence does not exceed 300 (Subtask B).

Input Data

The file INPUT.TXT contains 8 positive integers in the first line, the description of the target configuration.

Output Data

On the first line of file OUTPUT.TXT your program must write the length L of the transformation sequence. On the following L lines it must write the sequence of identifiers of basic transformations, one letter in the first position of each line.

Tool

MTOOL.EXE is a program in the task directory that lets you play with the magic squares. By executing "mtool input.txt output.txt" you can experiment with the target configuration and the sequence of transformations.

Example Input and Output


INPUT.TXT               OUTPUT.TXT     

2 6 8 4 5 7 3 1         7
                        B
                        C
                        A
                        B
                        C
                        C
                        B

Figure 5: Example Input and Output