Copiado al portapapeles
Descripción
Thanos sort es un algoritmo de ordenamiento, que funciona de la siguiente manera:
Si la arreglo no está ordenado, chasquee los dedos* para eliminar la primera o la segunda mitad de los elementos y repita el proceso hasta que el arreglo quede ordenado.
Dado un arreglo de números enteros, se pide determinar ¿cuál es el tamaño de la arreglo ordenado más largo que puede obtener utilizando Thanos sort?
Después de cada chasquido, es opcional con que arreglo quedarse si con la parte derecha o izquierda. Siempre se busca obtener la longitud del arreglo mas grande (ordenado ascendentemente) debido esto elección de con cuál parte quedarse no debe ser tomado a la ligera.
Entrada
La primera línea de entrada contiene un solo número entero ( 1<=n<=512 ), el tamaño del arreglo. Se garantiza que n es una potencia de 2.
La segunda línea de entrada contiene enteros separados por espacios ai ( 1<=ai<=100 ), los elementos de la arreglo.
Salida
Imprimir la longitud máxima de un arreglo ordenado que puede obtener utilizando Thanos sort. Los elementos del arreglo deben ordenarse de forma ascendente.
Ejemplo Entrada
8 6 69 46 53 23 80 22 90
Ejemplo Salida
2
Ayuda
Para el ejemplo
[6, 69, 46, 53, 23, 80, 22, 90]
como el arreglo no esta ordenado, con un chasquido thanos elimina la mitad de los elementos del arreglo obteniendo:
[6, 69, 46, 53] o [23, 80, 22, 90]
Tomando el arreglo:
[6, 69, 46, 53]
con otro chasquido thanos elimina la mitad de los elementos de un arreglo
[6, 69] o [46,53]
nos quedamos con el arreglo
[46,53]
y longitud del arreglo es 2