C++ - Cantidad de veces que hay que aplicar un movimiento para que el array quede igual de ordenado
Publicado por Borja Aday Guadalupe Luis (1 intervención) el 11/10/2018 11:46:29
Tengo que realizar un programa en C++ que haga lo siguiente:
Puedes encontrar el ejercicio en: https://www.aceptaelreto.com/problem/statement.php?id=324
La entrada estará compuesta por distintos casos de prueba. Cada uno de ellos consta de dos líneas, una primera
con el número de elementos y otra indicando qué movimiento de moléculas se realiza.
El movimiento viene definido con n enteros que indican, para cada posición de una molécula, en qué posición termina la molécula que ocupaba ese lugar.
Ejemplo:
4
2 1 4 3
De esta forma al aplicar el movimiento por primera vez quedaría:
1 2 3 4
Al aplicar el movimiento por segunda vez:
2 1 4 3
Por tanto la salida de este ejemplo es 2 pues si haces dos veces el mismo movimiento queda igual que como estaba al principio.
Matemáticamente se soluciona calculando cuando tarda cada posición en volver a su sitio y hallando el mínimo común múltiplo de todos esos valores pero es muy costoso de programar y tardaría demasiado la ejecución, seguro hay una solución más sencilla que me pierdo, si alguien me puede ayudar se lo agradezco.
Otros ejemplos:
3
1 2 3
Solución: 1
3
2 3 1
Solución: 3
Un saludo !
Puedes encontrar el ejercicio en: https://www.aceptaelreto.com/problem/statement.php?id=324
La entrada estará compuesta por distintos casos de prueba. Cada uno de ellos consta de dos líneas, una primera
con el número de elementos y otra indicando qué movimiento de moléculas se realiza.
El movimiento viene definido con n enteros que indican, para cada posición de una molécula, en qué posición termina la molécula que ocupaba ese lugar.
Ejemplo:
4
2 1 4 3
De esta forma al aplicar el movimiento por primera vez quedaría:
1 2 3 4
Al aplicar el movimiento por segunda vez:
2 1 4 3
Por tanto la salida de este ejemplo es 2 pues si haces dos veces el mismo movimiento queda igual que como estaba al principio.
Matemáticamente se soluciona calculando cuando tarda cada posición en volver a su sitio y hallando el mínimo común múltiplo de todos esos valores pero es muy costoso de programar y tardaría demasiado la ejecución, seguro hay una solución más sencilla que me pierdo, si alguien me puede ayudar se lo agradezco.
Otros ejemplos:
3
1 2 3
Solución: 1
3
2 3 1
Solución: 3
Un saludo !
Valora esta pregunta
0