IOI '96 - Veszprém, Hungary

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. Moreover, construct a sequence of exchange operations for the respective sorting.

Input Format

The first line of input contains the number of records N (1 ≤ N ≤ 1000). Each of the following N lines contains a key value.

Output Format

The first line of output should contain the minimal number L of exchange operations needed to make the sequence sorted. 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. Positions are denoted by the numbers from 1 to N.

Note: The answer is not necessarily unique. Your program is only required to find one possible sequence of exchanges.

Sample Input

9
2
2
1
3
3
3
2
3
1

Sample Output

4
1 3
4 7
9 2
5 9

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 32M
Added: Dec 22, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I think the problem isn't being graded properly. My solution works on USACO and gives correct outputs for all the input files available at ioinformatics.org. The same solution gets 10/100 here. Please help.

You did not read the problem statement. This is the original IOI problem where you must output an actual sequence of exchanges. The USACO version is modified to only have you output L.