Se nos da una lista de enteros p1, ..., pk (no necesariamente distintos) donde cada uno tiene un valor entre 1 y 9, inclusive. Usando cada uno de los p1, ..., pk exactamente una vez, podemos formar concatenaciones de dígitos, para lograr una nueva lista de números; Luego sacamos el producto de esta nueva lista. El objetivo es maximizar este producto eligiendo las mejores concatenaciones de dígitos.
Por ejemplo, se nos da la lista: 2 3 2 (separados por espacios). Podemos formar las siguientes concatenaciones:
2 3 2
(producto de estas concatenaciones es12
)23 2
(producto es46
)32 2
(producto es64
)22 3
(producto es66
)
Dado que el producto más grande que podemos formar de concatenaciones es 66, lo sacamos.
Reglas:
- Debe haber al menos una multiplicación (es decir, no puede concatenar todos los dígitos y generarlos).
- No puede usar ningún otro operador que no sea la multiplicación, o insertar paréntesis, etc.
- Suponga que la lista de enteros dada está separada por espacios, y todos los enteros tienen valores entre 1 y 9.
¡El código más corto (en bytes) gana!
Casos de prueba:
Entrada 1 2 3
:; Salida: 63
(es decir, 21*3
)
Entrada 2 5 9
:; Salida: 468
( 52*9
)
Entrada 1 2 3 4
:; Salida: 1312
( 41*32
)
Respuestas:
CJam,
32282312 bytesPruébelo en línea en el intérprete de CJam .
¡Gracias a @ user23013 por ayudarme a guardar 16 bytes completos!
Idea
Permutar los caracteres en la cadena de entrada lo divide en enteros (grupos de dígitos consecutivos) separados por espacios. Al presionar un cero y luego evaluar la cadena de entrada permutada, empujamos dos o más enteros. Multiplicar los dos más altos dará como resultado el producto de la entrada dividido en exactamente dos enteros o algún valor subóptimo.
Código
fuente
l2%_,,1>\e!m*{~S+m<~*}%$W=
.l2%S+e!{0\~*}%$W=
.CJam,
3635 bytesMuy claro. Repite todas las combinaciones posibles y las ordena por producto. Luego sale el más grande. Todo esto, teniendo en cuenta que al menos 1 multiplicación debe estar presente.
Agregará una explicación pronto.
Pruébalo en línea aquí
fuente
JavaScript (ES6) 125
Editar Creo que @oberon lo hizo bien: "cada nuevo dígito debe concatenarse al número más pequeño"
No cambiaré esta respuesta robando su idea. La implementación en ES6 sería de 70 bytes (el signo cambió en comparación para comparar como número y no cadenas)
Mi solución
Como dije en los comentarios, para cada par de números a, b, el producto a * b es menor que la concatenación simple ab (= a * 10 ^ (dígitos de b) + b). Por lo tanto, es mejor evitar productos y preferir la concatenación, pero como se solicita al menos 1 producto, tenemos que construir 2 números y multiplicarlos.
Intento todos los grupos posibles de dígitos, construyendo un par de números para multiplicar. Cada número se construye obviamente tomando dígitos en orden decreciente.
Por ejemplo, con una lista de 4 números, [1 2 3 4] - intente:
El máximo de estos valores es el resultado que necesitamos.
Las agrupaciones se pueden enumerar en bucle en un mapa de bits de 4 bits, con un valor mínimo 0001 y un valor máximo 0111 (es decir, 1 << (4 -1) - 1)
No tan golfizado
Prueba usando el fragmento de abajo en Firefox.
fuente
Python 3, 111 bytes
Probablemente sea mucho más golfable. Sin embargo, me gusta su tiempo de ejecución (O ( n log n ), ¿verdad?).
Ungolfed con explicación.
fuente
Pyth, 25 bytes
Doy vueltas sobre cada permutación de la entrada. Entonces, como cada combinación óptima consta de dos enteros, simplemente la dividí en cada posición posible y multipliqué las divisiones concatenadas. Luego ordeno y obtengo el último elemento.
fuente
R, 164
Como método, no estoy seguro de si esto es robusto. Con los casos que he probado, parece funcionar cada vez. Intenté probarlo con la solución de optimizadores y parece estar bien también con eso. Estoy más que preparado para demostrar que estoy equivocado :) Hay espacio para jugar al golf, pero esperaba obtener algunos comentarios sobre el método primero.
El proceso general es:
Ampliado con algunos comentarios
Y algunas ejecuciones de prueba (implementadas como una función llamada g)
fuente