Su tarea es, dado un número entero positivo n
, generar una expresión que sea igual al número n
.
El problema es: solo se le permite el número 1
en la salida.
Los operadores a su disposición son:
+
`-
`*
y/
/
es la división de punto flotante (so5/2 = 2.5
).
sqrt
(comos
)ceil
yfloor
(comoc
yf
respectivamente)!
(factorial)- El factorial, en este caso, solo funciona para enteros positivos.
También puede apilarlos 1
juntos, por lo que algo como esto 11
es aceptable en la salida. Sin embargo, cuentan como el mismo número de 1
's que hay en el número (entonces 11
cuenta como 2 1
' s).
También debe incluir corchetes en la salida, de modo que la expresión en la salida, cuando se ejecute a través del orden de las operaciones, dé como resultado la entrada. Sin embargo, no cuentan como operaciones.
Ejemplos:
- Entrada = 24, una salida posible =
(1+1+1+1)!
- Entrada = 11, una salida posible =
11
- Entrada = 5, una salida posible =
c(s((1+1+1+1)!))
- El techo de la raíz cuadrada de
24
es5
.
- El techo de la raíz cuadrada de
Reglas:
- Se le garantiza que la entrada es un entero positivo desde
1
hasta2^31-1
. - Su programa debe funcionar para cualquier número entero positivo hasta
2^31-1
, incluso si no se prueban. - Su programa debe terminar de procesar todas las salidas para todos los números en el conjunto en 1 hora.
- Los resultados para cada ejecución del programa deben ser exactamente los mismos, además, sin semillas.
- Solo puede codificar las expresiones para un máximo de 10 valores numéricos.
- No está permitido tener números imaginarios en ninguna parte de la salida (así que no
s(some negative number)
). - Tampoco se le permite tener números mayores
2^31-1
o menores que-2^31+1
en cualquier parte de la salida, incluso cuando estánsqrt
editados o/
ed (así que no(((1+1+1)!)!)!
o((1+1+1+1)!)!
).
Conjunto de números:
945536, 16878234, 32608778, 42017515, 48950830, 51483452, 52970263, 54278649, 63636656, 78817406, 89918907, 90757642, 95364861, 102706605, 113965374, 122448605, 126594161, 148064959, 150735075, 154382918, 172057472, 192280850, 194713795, 207721209, 220946392, 225230299, 227043979, 241011012, 248906099, 249796314, 250546528, 258452706, 276862988, 277140688, 280158490, 286074562, 308946627, 310972897, 322612091, 324445400, 336060042, 346729632, 349428326, 352769482, 363039453, 363851029, 392168304, 401975104, 407890409, 407971913, 425780757, 459441559, 465592122, 475898732, 482826596, 484263150, 506235403, 548951531, 554295842, 580536366, 587051904, 588265985, 588298051, 590968352, 601194306, 607771869, 618578932, 626776380, 667919873, 681786366, 689854904, 692055400, 697665495, 711608194, 734027104, 750869335, 757710567, 759967747, 777616154, 830071127, 833809927, 835873060, 836438554, 836945593, 863728236, 864158514, 871273503, 881615667, 891619600, 897181691, 918159061, 920521050, 924502226, 929983535, 943162304, 950210939, 950214176, 962610357, 974842859, 988572832
(Estos son 100 números aleatorios de 1 a 1 billón).
Sistema de puntuación:
Su puntaje se determina así:
- Su programa será probado contra los números aleatorios en el conjunto.
- Debe proporcionar el resultado generado utilizando los números aleatorios en el conjunto (ya sea dentro de su respuesta o como un enlace pastebin).
- Entonces tiene dos "puntajes": un puntaje primario y un puntaje secundario.
- Tu puntaje principal es
(no. of 1's in output)*(no. of operators in output)
. Si su puntaje principal es el más bajo, usted gana. - Su puntaje secundario es el momento de su carga, en GMT, y en 24 horas. Entonces, si sube su programa el 12 de septiembre a las 00:00 GMT, su puntaje es
12/09/2016, 00:00
(useDD/MM/YYYY HH:MM
para su formateo).
- Tu puntaje principal es
Muestra tu puntaje así:
(language name)
Primary Score = (primary score)
Secondary Score = (secondary score)
(no. of 1's) `1`'s, (no. of operators) operators
Reemplace todas las cosas entre paréntesis con su nombre de idioma, puntaje primario y puntaje secundario respectivamente.
Ganador actual:
El ganador actual es @ChrisJefferson, quien tiene un puntaje principal de 3,810,660
.
fuente
Respuestas:
C ++ 11
Pequeña actualización adicional: agregue mucho menos y pruebe todos los números del formulario A * B + C. Creo que, dentro del límite de tiempo, esto es bastante óptimo, suponiendo que solo use
+
,*
y!
. ¡Dejo otros operadores a personas con más tiempo que yo!Pequeña actualización: trate de utilizar factores y números como 11 ... 111. También solucioné un error que no estaba contando
!
en mi costeoNuevo resultado:
Puntaje primario = 3,810,660
Puntaje secundario = 12/09/2016 20:00
2532
1
s, 1505 operadores.Varios trucos juntos. Mi programa comienza estableciendo el programa más corto para todos los factores y números de la forma 111..111 (no creo que esto incumple la regla de cableado, ya que estas son las formas más cortas de hacer estos números. Podría reorganizar mi código, así que verifico estos patrones en mi programación dinámica si lo desea). Luego, realice un enfoque de programación dinámica parcial, probando varias formas:
Desafortunadamente, no puedo probar todas las formas de descomponer un número, así que elijo factorial y 11 ... 11 para probar solo el número más cercano, para A + B para probar cosas cerca de A / 2 y para A * B + C para probar solo As bastante pequeño.
Sería fácil extender esto para intentar algunos '-s, tratando de sobrepasar ligeramente a veces (particularmente en A * B - C), pero me gusta solo tratar de crecer.
Además, es muy difícil optimizar la condición de optimización (¡no me gusta!) Porque, en principio, no se puede encontrar el "mejor" valor para cada número de forma aislada, debe considerar su conjunto de respuestas a nivel mundial (que no tengo la intención de hacer).
Advertencia: Este programa necesita una máquina de 64 bits y alrededor de 10 GB de memoria (ya que ineficientemente hago una matriz gigante para todos los resultados parcialmente calculados).
Programa:
Resultados:
fuente
!
. Creo que son 1632 operadores, no 1407. (Sin embargo, lo que aún conduce a una gran puntuación).long maxval
gruñir gruñirHaskell
Puntuación primaria: 27242281
Puntuación secundaria: 12/12/2016 09:01
11891
1
's, 2291 operadoresBásicamente encuentra la forma más corta de hacerlo usando solo + y -
Salida:
fuente
Python, puntaje 17136288
puntaje secundario: 09/12/2016 08:53
(4784 unidades y 3582 operaciones)
Trabajo en progreso pero OP solicitó mi código actual ...
Salida - Tenga en cuenta que
t
es la función factorial, para que no se debe confundir conf
porfloor
si se acostumbra - evalué cada uno usando la funciónt
(arriba) para corroborar que todos ellos son correctos:fuente
t
s en la salida?JavaScript (ES6), 27212498, 2016-09-12 09: 46: 34Z
Solo usa + y -. Basado en mi respuesta para minimizar esos
fuente
Pitón
Puntuación primaria = 2214138604871819402525
Puntuación secundaria = 12/09/2016, 07:53
Aquí está el código:
Solo para que la pelota ruede.
Básicamente salidas
1+1+1...+1
, donde el número de1
's en la expresión de salida es igual an
.En total, hay
47054634305
1
's para el conjunto de números y47054634205
operadores (que son todos+
).No voy a publicar un pastebin aquí, porque entiendes la idea.
fuente
2**31-1
.n-1
? Funciona bien para mí.awk
puntaje primario 46933701
puntaje secundario 09/12/2016 19:20
(6901 unidades, 6801 operaciones)
Simplemente imprime la representación binaria calculada de izquierda a derecha.
Por ejemplo, 19 es 10011, que es ((((( 1 ) * 2 + 0 ) * 2 + 0 ) * 2 + 1 ) * 2 + 1 ).
Solo dejo el
+0
y escribo el2
como(1+1)
.Solo tenía curiosidad acerca de cómo sería este método.
Salida:
fuente
Python 3
Puntuación primaria:
69720516
Puntuación secundaria:
09:30 14/09/2016
Editar: ahora usa la multiplicación para reducir en gran medida la puntuación.
Esto hace un gran uso de factoriales y recursividad. En total, el programa usa:
5958
unos11702
operadoresIdeone it!
fuente
JAVA
Puntaje primario
1045978739
Puntaje secundario
12/09/2016 16:05
37193
1s
28123
operators
fuente
1
al comienzo de cada uno(1*11*11*...*11)
.Emacs Lisp
Puntuación primaria: 81638725
Puntuación secundaria: 09/12/2016 09:35
Básicamente construye una suma sobre el dominio (1, 11, 111, ...) que es equivalente a n.
fuente
111+11+1+1
, ¿verdad? (1
correos electrónicos en toda la salida de 100 números y los ha multiplicado por el número total de+
operaciones en toda la salida?AWK , 15642720
Puntuación secundaria = 30/05/2017, 21:11
Pruébalo en línea!
Unos: 4590
Ops: 3408 Puntuación primaria = 15642720 Puntuación secundaria = 30/05/2017 21:11
fuente