In this task the possible key values are the integers 1, 2 and 3. The required sorting order is nondecreasing. 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 1Figure 1
{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
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: 

B: 

C: 

Figure 4: Basic transformations
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).
The file INPUT.TXT contains 8 positive integers in the first line, the description of the target configuration.
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.
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.
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