Download Description

Caribbean Online Judge
3019 - Another Sorting Problem II
Description
A permutation of the integers between 1 and N is given. Initially, they are positioned in an arbitrary
order, but you want to rearrange the numbers, leaving them in increasing order. To do so, you use
the following procedure/steps:
1. First, pick a number which is not in their corresponding position; select always the option/number
coming first in the sequence (as far to the left as possible).
2. Then, move this number into its corresponding position. Another number may be occupying this
location, so you must also move this number to its correct position. Repeat this step while
possible.
3. Finally, repeat from the first step while possible.
Once these steps finish, the sequence will be ordered. Knowing the amount of affected numbers
during this sorting procedure results an easy task. A number is considered affected if their initial
position is distinct to their final position.
Then, instead of that, you want to know the total cost of the sorting process. The total cost is equal
to the sum of the cost of each independent moving operation. And the cost of each moving
operation is equal to the absolute difference between previous and final position of the element
which is moved. Note that if an element remains in their original position, then it represents no cost
for the sorting process.
Se da una permutación de los números enteros entre 1 y N. Inicialmente, se colocan en un orden
arbitrario, pero se quiere reorganizar los números, dejándolos en orden creciente. Para ello, se
utiliza el siguiente procedimiento / pasos:
1. En primer lugar, elegir un número que no está en su posición correspondiente; seleccionar
siempre la opción / número que viene primero en la secuencia (lo más a la izquierda como sea
posible).
2. A continuación, pasar este número en su posición correspondiente. Otro número puede estar
ocupando esa ubicación, por lo que también debe mover este número a su posición correcta.
Repita este paso mientras sea posible.
3. Por último, repita el proceso desde el primer paso, mientras sea posible.
Una vez que estos pasos terminen, la secuencia estará ordenada. Conocer la cantidad de números
afectados durante este procedimiento de ordenación resulta una tarea fácil. Un número se
considera afectado si su posición inicial es distinta a su posición final.
Entonces, en vez de eso, usted quiere saber el costo total del proceso de ordenación. El costo total
es igual a la suma del costo de cada operación de movimiento independiente. El costo de cada
operación de movimiento es igual a la diferencia absoluta entre la posición inicial y final del
-1-
Caribbean Online Judge
elemento que se mueve. Note que si un elemento permanece en su posición original, entonces
representa un costo nulo para el proceso de ordenación.
Input specification
The first line contain a integer number T (1 <= T <= 100), the number of test
cases. For each case:
•The first line contains an integer number N (1 <= N <= 50), the number of integers in the sequence.
•The second line contains N space-separated integer numbers, a permutation of the numbers
between 1 and N.
La primera línea contiene un número entero T (1 <= T <= 100), el número de casos de prueba.
Para cada caso:
•La primera línea contiene un número entero N (1 <= n <= 50), el número de enteros en la
secuencia.
•La segunda línea contiene N números enteros separados por un espacio, una permutación de los
números entre 1 y N.
Output specification
For each case, you must print a line with total cost of the sorting process.
Para cada caso, se debe imprimir una línea con el costo total del proceso de
ordenación.
Sample input
3
1
1
5
2 3 1 5 4
9
3 2 1 5 4 7 8 6 9
Sample output
0
6
10
-2-
Caribbean Online Judge
Hint(s)
Source
[Yonny Mondelo Hernández]
Added by
ymondelo20
Addition date
2014-10-14
Time limit (ms)
150000
Test limit (ms)
5000
Memory limit (kb)
256000
Output limit (mb)
64
Size limit (bytes)
15000
Enabled languages
Bash C C# C++ Java Pascal Perl PHP
Python Ruby Text
-3-