Pista 1

La operación permitida solo permite intercambiar dos huesos si sus tamaños tienen paridad distinta. Esto implica que un hueso par puede intercambiarse con cualquier hueso impar, y viceversa.

Pista 2

Si en el arreglo existen huesos de ambas paridades, entonces es posible reordenar completamente el arreglo. En cambio, si todos los huesos tienen la misma paridad, no se puede realizar ningún intercambio.

Solución

Para cada caso de prueba se analiza la paridad de los tamaños de los huesos.

Existen dos escenarios posibles:

• Todos los huesos tienen la misma paridad (todos pares o todos impares).
  En este caso, no es posible realizar ningún intercambio, ya que la operación requiere paridades distintas. Por lo tanto, el arreglo original ya es el único arreglo alcanzable y, en consecuencia, el arreglo lexicográficamente más pequeño.

• Existen huesos pares e impares.
  En este caso, cualquier hueso puede intercambiarse con cualquier otro usando huesos de paridad opuesta como intermediarios. Esto permite obtener cualquier permutación del arreglo, incluyendo el arreglo completamente ordenado.

Dado que el arreglo ordenado de menor a mayor es el lexicográficamente más pequeño posible, basta con ordenarlo cuando exista al menos un número par y uno impar.

Por lo tanto, el procedimiento consiste en establecer dos condiciones:

• Si el arreglo contiene ambas paridades, se ordena.
• En caso contrario, se imprime tal como está.

Procedimiento

1. Leer el número de huesos \(N\) y sus tamaños.
2. Verificar si existe al menos un número par y uno impar.
3. Si existen ambas paridades, ordenar el arreglo.
4. Imprimir el arreglo resultante.

Implementación en C++

Fido_y_los_Huesos.cpp

Complejidad

• Tiempo:
  Para cada caso de prueba, se recorre el arreglo una vez para verificar paridades.
  En el peor caso, se ordena el arreglo, lo que cuesta \(O(N log N)\).
  Considerando todos los casos de prueba \(T\), la complejidad total es \(O(T \cdot N \log N)\).

• Memoria:
  Se utiliza \(O(N)\) para almacenar el arreglo de huesos.