rohan2kool

Today there was an inter-school programming competition and I was there on my school team. There were a set of four questions, out of which we were able to do 3. The 4th question was a bit difficult and thereby we couldn't solve it in the given amount of time. Now, i'd like help frm u guys.. this is the question:

1. A list is to be sorted in an ascending order. The sorting has to take place via swaps only. Meaning, if there are two elements a and b at positions p and q in a list L, a swap at p and q would mean that a would be at position q and b would be at position a.

However, the elements in the list can have the values '1', '2' or '3' only. In that case, for a given list, there exists a optimal sequence of swaps which will result in a sorted array. Write a program which computes the minimum number of swaps required for a given list and also displays the swaps.

INPUT

The input will consist of an integer(0 < n < 10000) on a line, which specifies the number of elements in the list. All elements are integers. This will be followed by n lines, each line holding an element of the list.

OUTPUT

First line of the output should contain the minimum number of swaps (m) required to sort the given list. This should be followed by m lines, each line showing the swaps in the format: position-a <space> position-b, where position-a and position-b are the respective positions of the swapped elements in the given list.

EXAMPLE

[input]

9

2

2

1

3

3

3

2

3

1

[output]

4

1 3

4 7

2 9

9 5

We had to do this in C++.. bt any language would be fine. What i'm actually looking for is an algorithm to go about finding the minimum no. of swaps required.

1. A list is to be sorted in an ascending order. The sorting has to take place via swaps only. Meaning, if there are two elements a and b at positions p and q in a list L, a swap at p and q would mean that a would be at position q and b would be at position a.

However, the elements in the list can have the values '1', '2' or '3' only. In that case, for a given list, there exists a optimal sequence of swaps which will result in a sorted array. Write a program which computes the minimum number of swaps required for a given list and also displays the swaps.

INPUT

The input will consist of an integer(0 < n < 10000) on a line, which specifies the number of elements in the list. All elements are integers. This will be followed by n lines, each line holding an element of the list.

OUTPUT

First line of the output should contain the minimum number of swaps (m) required to sort the given list. This should be followed by m lines, each line showing the swaps in the format: position-a <space> position-b, where position-a and position-b are the respective positions of the swapped elements in the given list.

EXAMPLE

[input]

9

2

2

1

3

3

3

2

3

1

[output]

4

1 3

4 7

2 9

9 5

We had to do this in C++.. bt any language would be fine. What i'm actually looking for is an algorithm to go about finding the minimum no. of swaps required.