Use of Netscape (Version 2.0 or later) is recommended.

8th International Olympiad in Informatics, Veszprém, Hungary

IOI'96 Day 2
Tasks

1. Sorting a Three-Valued Sequence - 2. Longest Prefix - 3. Magic Squares

Sorting a Three-Valued Sequence

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).

Input Data

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.

Output Data

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.

Example Input and Output

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

Longest Prefix

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.

Input Data

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.

Output Data

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.

Example Input and Output

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

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