TLE '16 Contest 6 (Mock CCC) S4 - Bubble Sort
Since the Canadian Computing Competition (CCC) often requires the use of a sorting algorithm, Darcy needs to practice sorting! Darcy's favourite sorting algorithm is bubble sort.
To practice his ability to bubble sort, he gathers up an array which contains integers. He accesses this array by calling as the first element, and as the last element. Every element in this array is an integer in the range , and there are no duplicate elements.
Darcy swaps adjacent elements to sort this array, but if , he does not want to swap the integer ever again. Specifically, Darcy is allowed to swap the elements and if these following conditions hold:
- The first index is valid ()
- The second index is valid ()
- Darcy can swap the element at the first index ()
- Darcy can swap the element at the second index ()
Eventually, Darcy gets confused and asks for help. Is there a sequence of swaps that will sort ? In the case that no sequence exists, output
The first line contains the integer .
The second line contains space-separated integers, which are the elements of . These integers are between and , inclusive. Every element in the array is distinct.
- For 3 of the 15 available marks, the elements of are in descending order.
- For an additional 2 of the 15 available marks, all multiples of are put in the correct index. Specifically, .
- For an additional 2 of the 15 available marks, .
- For an additional 4 of the 15 available marks, .
If it is impossible to sort the array , output
Otherwise, output the number of swaps needed to sort the array. Let this number be called . Your integer must not exceed million (). You do not have to print the lowest possible .
On the next lines of output, print two indices and . This indicates that and will be swapped in this step.
Sample Input 1
2 0 1
Sample Output 1
Explanation for Sample Output 1
The array is already sorted, so no swaps are necessary.
Sample Input 2
5 4 3 2 1 0
Sample Output 2
Explanation for Sample Output 2
Darcy does not want to swap the integer because . As a result, the remaining integers cannot be swapped to their proper indices. This array is impossible to sort.
Sample Input 3
6 2 5 1 4 0 3
Sample Output 3
13 3 2 3 2 3 2 4 3 1 2 2 3 3 4 4 5 1 2 2 3 3 4 0 1 1 2
Explanation for Sample Output 3
The table shows array as the instructions are performed. Notice that the bubble sort algorithm can be used after the swap.