Considere una lista l
, que consta de números. Definir una operación de bloque en el índice i
en la lista l
para ser el acto de mover 3 elementos consecutivos a partir de i
en l
hasta el final.
Ejemplo:
l, i (1-indexing) -> l (after applying block operation at index i)
[1,2,3,4,5], 1 -> [4,5,1,2,3]
[1,2,3,4,5,6,7], 3 -> [1,2,6,7,3,4,5]
Dada una lista que consta de solo 0 y 1, su desafío es dividirla de modo que los ceros estén al frente y los que están al final, usando solo operaciones de bloque. La salida debe ser los índices en el orden en que se aplican en la lista.
Como esto es imposible para la lista [1,0,1,0]
, se garantiza que la longitud de la lista sea de al menos 5.
Casos de prueba (1 indexación)
(hay otras salidas válidas)
[1,1,1,0,0] -> [1]
[0,1,0,1,0] -> [1,2,1,1]
[0,0,0,1,1,1,0,0,0] -> [4]
Use este script para generar más casos de prueba. (sólo de entrada. La rplc ' ';','
parte se utiliza para r e pl un c e espacios con comas en la salida)
Criterios ganadores
el desafío de código es el principal criterio ganador, y el código más rápido es el desempate. En particular:
- La solución con la longitud de salida más corta (menor número de operaciones de bloque) con el caso de prueba (
n_elem
= 500,random_seed
= {valor secreto}) gana. Debería poder ejecutar su solución hasta el final con el caso de prueba (n_elem
= 500,random_seed
= 123456). - En caso de empate, la solución que puede manejar el mayor valor de potencia de 2
n_elem
conrandom_seed
= {valor secreto} en 10 segundos (para mí) gana. - En caso de empate, la solución que lleva menos tiempo en ese caso de prueba gana.
fuente
Respuestas:
Python 3 , (0.397 n + 3.58) pasos
Regresión polinómica de 1000 puntos por
numpy.polyfit
.Pruébalo en línea!
fuente
Python 3, ~ 179 pasos para n = 500 (en promedio)
Un enfoque codicioso heurístico. Un poco lento pero aún funciona. Utiliza un solucionador óptimo para tamaños pequeños.
fuente