8th International Olympiad in Informatics, Veszprém, Hungary
IOI'96 Day 2
Problem 1: Sorting a Three-Valued Sequence
Return to Task Overview
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
