Sua tarefa é, dado um número inteiro positivo n
, gerar uma expressão que seja igual ao número n
.
O problema é: você só pode receber o número 1
na saída.
Os operadores à sua disposição são:
+
,-
,*
E/
/
é a divisão de ponto flutuante (so5/2 = 2.5
).
sqrt
(ass
)ceil
efloor
(comoc
ef
respectivamente)!
(fatorial)- O fatorial, neste caso, funciona apenas para números inteiros positivos.
Você também pode empilhar 1
, portanto, algo como 11
é aceitável na saída. No entanto, eles contam como o mesmo número de números 1
contidos no número (então 11
conta como 2 1
).
Você também deve incluir colchetes na saída, para que a expressão na saída, quando executada pela ordem das operações, resulte na entrada. Eles não contam como operações, no entanto.
Exemplos:
- Entrada = 24, uma saída possível =
(1+1+1+1)!
- Entrada = 11, uma saída possível =
11
- Entrada = 5, uma saída possível =
c(s((1+1+1+1)!))
- O teto da raiz quadrada de
24
é5
.
- O teto da raiz quadrada de
Regras:
- Você está garantido que a entrada é um número inteiro positivo de
1
a2^31-1
. - Seu programa deve funcionar para qualquer número inteiro positivo até
2^31-1
, mesmo que não seja testado. - Seu programa deve concluir o processamento de todas as saídas para todos os números do conjunto em 1 hora.
- Os resultados para cada execução do programa devem ser exatamente os mesmos - também, sem sementes.
- Você só pode codificar as expressões para um máximo de 10 valores numéricos.
- Você não tem permissão para ter números imaginários em nenhum lugar da saída (portanto, não
s(some negative number)
). - Também não é permitido que você tenha números maiores
2^31-1
ou menores que-2^31+1
em qualquer lugar da saída, mesmo quando eles sãosqrt
editados ou/
editados (portanto, nenhum(((1+1+1)!)!)!
ou((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
(Estes são 100 números aleatórios de 1 a 1 bilhão.)
Sistema de pontuação:
Sua pontuação é determinada assim:
- Seu programa será testado contra os números aleatórios no conjunto.
- Você deve fornecer a saída gerada usando os números aleatórios no conjunto (dentro da sua resposta ou como um link para colar).
- Você então tem duas "pontuações": uma pontuação primária e uma pontuação secundária.
- Sua pontuação principal é
(no. of 1's in output)*(no. of operators in output)
. Se sua pontuação principal for a mais baixa, você ganha. - Sua pontuação secundária é o horário do seu upload, no GMT e no período de 24 horas. Portanto, se você fizer o upload do seu programa em 12 de setembro, 00:00 GMT, sua pontuação será
12/09/2016, 00:00
(useDD/MM/YYYY HH:MM
para a sua formatação).
- Sua pontuação principal é
Mostre sua pontuação assim:
(language name)
Primary Score = (primary score)
Secondary Score = (secondary score)
(no. of 1's) `1`'s, (no. of operators) operators
Substitua todas as coisas entre parênteses pelo nome do seu idioma, pontuação primária e pontuação secundária, respectivamente.
Vencedor atual:
O vencedor atual é @ChrisJefferson, que tem uma pontuação primária de 3,810,660
.
fonte
Respostas:
C ++ 11
Pequena atualização adicional: adicione muito menos e tente todos os números do formulário A * B + C. Eu acredito que, dentro do prazo, este é bastante próximo ao ideal, supondo que você use somente
+
,*
e!
. Deixo outros operadores para pessoas com mais tempo do que eu!Pequena atualização: tente usar fatoriais e números como 11 .... 111. Também foi corrigido um erro que eu não contava
!
no meu custoNovo resultado:
Pontuação primária = 3.810.660
Pontuação secundária = 09/09/2016 20:00
2532
1
s, 1505 operadores.Vários truques juntos. Meu programa começa definindo o programa mais curto para todos os fatoriais e números do formulário 111..111 (não acho que isso se enquadre na regra da instalação elétrica, pois essas são as maneiras mais curtas de fazer esses números. meu código para verificar esses padrões na minha programação dinâmica, se você quiser). Em seguida, faça uma abordagem de programação dinâmica parcial, tentando várias formas:
Infelizmente, eu não posso tentar todas as maneiras de decompor um número, então escolhi fatorial e 11 ... 11 para tentar apenas o número mais próximo, para A + B tentar coisas próximas de A / 2 e para A * B + Tentar apenas muito pequeno.
Seria fácil estender isso para tentar alguns '-'s, tentando ultrapassar um pouco às vezes (principalmente em A * B-C), mas eu gosto muito de apenas tentar crescer.
Além disso, é muito difícil otimizar a condição de otimização (não gosto!) Porque, em princípio, você não pode criar um "melhor" valor para cada número isoladamente, é necessário considerar seu conjunto de respostas globalmente (o que não pretendo fazer).
Aviso: Este programa precisa de uma máquina de 64 bits e cerca de 10 GB de memória (como eu ineficientemente faço uma matriz gigante para todos os resultados parcialmente computados).
Programa:
Resultados:
fonte
!
. Eu acho que é de 1632 operadores, e não 1407. (que ainda leva a uma grande pontuação, no entanto.)long maxval
resmungar resmungarHaskell
Pontuação primária: 27242281
Pontuação secundária: 12/09/2016 09:01
11891
1
's, 2291 operadoresEle basicamente encontra a maneira mais curta de fazê-lo usando apenas + e -
Resultado:
fonte
Python, pontuação 17136288
nota secundária: 12/09/2016 08:53
(4784 operações e 3582 operações)
Trabalho em andamento, mas o OP solicitou meu código atual ...
Saída - observe que essa
t
é a função fatorial, para não confundir com,f
poisfloor
se for usada - avaliei cada uma usando a funçãot
(acima) para verificar novamente se estão corretas:fonte
t
s na saída?JavaScript (ES6), 27212498, 12/09/2016 09: 46: 34Z
Usa apenas + e -. Com base na minha resposta para minimizar aqueles
fonte
Pitão
Pontuação primária = 2214138604871819402525
Pontuação secundária = 12/09/2016, 07:53
Aqui está o código:
Apenas para fazer a bola rolar.
Basicamente
1+1+1...+1
, saídas , onde o número de1
's na expressão emitida é igual an
.No total, existem
47054634305
1
para o conjunto de números e47054634205
operadores (que são todos+
).Não vou postar uma pasta aqui, porque você entendeu.
fonte
2**31-1
.n-1
? Isso funciona bem para mim.awk
escore primário 46933701
resultado secundário 12/09/2016 19:20
(6901 unidades, 6801 operações)
Simplesmente imprime a representação binária calculada da esquerda para a direita.
Por exemplo 19 é 10011, que é ((((( 1 ) * 2 + 0 ) * 2 + 0 ) * 2 + 1 ) * 2 + 1 )).
Eu apenas deixo de fora
+0
e escrevo o2
as(1+1)
.Eu só estava curioso sobre como esse método seria pontuado.
Resultado:
fonte
Python 3
Pontuação Primária:
69720516
Pontuação Secundária:
09:30 14/09/2016
Editar: agora usa multiplicação para reduzir bastante a pontuação.
Isso faz um ótimo uso de fatoriais e recursão. No total, o programa usa:
5958
uns11702
operadoresIdeone it!
fonte
JAVA
Pontuação Primária
1045978739
Pontuação secundária
12/09/2016 16:05
37193
1s
28123
operators
fonte
1
no início de cada um(1*11*11*...*11)
.Emacs Lisp
Pontuação primária: 81638725 Pontuação secundária : 09/09/2016
09:35
Constrói basicamente uma soma sobre o domínio (1, 11, 111, ...) que é equivalente a n.
fonte
111+11+1+1
, certo? (Corrija-me se eu estiver errado.)1
s em toda a saída de 100 números e multiplicou isso pelo número total de+
operações em toda a saída?AWK , 15642720
Pontuação secundária = 30/05/2017, 21:11
Experimente online!
Uns: 4590
Ops: 3408 Pontuação primária = 15642720 Pontuação secundária = 30/05/2017 21:11
fonte