A tarefa
Dado um número inteiro positivo de entrada n
(de 1 até o limite do seu idioma, inclusive), retorne ou produza o número máximo de números inteiros positivos distintos que somam n
.
Casos de teste
Vamos f
definir uma função válida de acordo com a tarefa:
A sequência para f
, começando em 1:
1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, ...
Como um caso de teste maior:
>>> f(1000000000) // Might not be feasible with brute-forcers
44720
Código de teste
Para quaisquer casos de teste não fornecidos explicitamente, a saída do seu código deve corresponder ao resultado do seguinte:
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
System.out.println((int) Math.floor(Math.sqrt(2*x + 1./4) - 1./2));
}
}
code-golf
math
number-theory
integer
integer-partitions
Addison Crump
fonte
fonte
Respostas:
05AB1E , 4 bytes
Experimente online!
Ferramenta perfeita para o trabalho.
ÅT
origina o lista de Å ll t números riangular até e incluindo o N (infelizmente inclui também 0, caso contrário, seria de 3 bytes),g<
recebe o len g th e diminui-la.fonte
Gelatina ,
65 bytesExperimente online!
Um pouco eficiente. Essa sequência é incrementada em números triangulares, portanto, isso conta apenas quantos números triangulares são menores que n .
Explicação:
fonte
Haskell , 26 bytes
-2 bytes graças a H.PWiz.
Experimente online!
Isso retorna o enésimo elemento dos números inteiros, onde cada i é replicado i + 1 vezes.
fonte
succ
significasuccessor
.Brain-Flak , 36 bytes
Experimente online!
Isso usa a mesma estrutura que o algoritmo de divisão padrão, exceto que o "divisor" é incrementado toda vez que é lido.
fonte
Pari / GP , 19 bytes
Experimente online!
fonte
Flacidez Cerebral , 82 bytes
Espaço em branco adicionado para "Legibilidade"
Experimente online!
fonte
Geléia , 7 bytes
Experimente online!
Geléia , 9 bytes
Experimente online!
Isso é mais longo que o de
Dennise DJ, mas desta vez de propósito . Muito, muito eficiente .fonte
M
.R , 28 bytes
Experimente online!
Cria o vetor de tempos
1
repetidos2
, tempos2
repetidos3
, ..., temposn
repetidosn+1
e pega onth
elemento. Isso causará erro de memória porque1:n
é muito grande ou porque a lista repetida comn*(n+1)/2 - 1
elementos é muito grande.R , 29 bytes
Experimente online!
Calcula o valor diretamente, usando a fórmula encontrada na resposta de alefalpha . Isso deve ser executado sem problemas, além da precisão numérica possivelmente.
R , 30 bytes
Experimente online!
Conta os números triangulares menores ou iguais a
n
. Isso possivelmente causará um erro de memória se1:n
for grande o suficiente - por exemplo,1e9
ele lançaError: cannot allocate vector of size 3.7 Gb
.fonte
APL (Dyalog) , 8 bytes
Experimente online!
fonte
TI-Basic, 12 bytes
fonte
JavaScript (Node.js) , 18 bytes
Experimente online!
fonte
floor((sqrt(8x+4)-1)/2)
(sua fórmula) efloor((sqrt(8x+1)-1)/2)
(fórmula correta) dão o mesmo resultado para todosx
.Japonês , 8 bytes
Solução de fórmula fechada.
Tente
Explicação
Multiplique por 8, adicione 1 (
Ä
), obtenha a raiz quadrada (¬
), subtraia 1 (É
) e o piso divida o resultado por 2 (z
).Alternativa, 8 bytes
Porto da solução Jelly DJMcMayhem .
Tente
Gere uma matriz de números inteiros (
õ
) de 1 para entrada, reduza cumulativamente (å
) por adição (+
) e conte (è
) os elementos que são menores ou iguais a (§
) a entrada (U
).fonte
Befunge,
3220 bytesExperimente online!
fonte
Flacidez Cerebral ,
705648 bytesExperimente online!
Explicação
A parte principal disso é o seguinte snippet que escrevi:
Isso não fará nada se o TOS for positivo e alternar as pilhas caso contrário. É super stack impuro, mas funciona. Agora, a parte principal do programa subtrai números cada vez maiores da entrada até que a entrada não seja positiva. Iniciamos o acumulador em 1 cada vez que subtraímos mais 1 do que o acumulador da entrada.
Podemos colocar isso dentro do snippet acima
Isso é colocado em um loop e é executado até trocarmos de pilhas. Quando o loop termina, recuperamos o acumulador trocando pilhas e removendo o lixo.
fonte
Pitão , 7 bytes
Experimente online!
Mantenha filtro as partições inteiras que são
I
diferentes da desduplicação, agarre oh
cabeçote e obtenha seul
ength.Prova de validade
Não é muito rigoroso nem bem formulado.
Deixe A = um 1 + A 2 + ... + um n e B = b 1 + b 2 + ... + b m ser duas partições distintas do mesmo número inteiro N . Vamos assumir que A é a partição exclusiva mais longa . Depois que a desduplicar B , isto é, substituir múltiplas ocorrências da mesma inteiro com apenas um deles, sabemos que a soma de B é menos do que N . Mas também sabemos que o resultado da função está aumentando (não estritamente), para que possamos deduzir que a partição exclusiva mais longa A sempre tem pelo menos a mesma quantidade de elementos que a contagem de itens exclusivos em outras partições.
fonte
Triangularidade , 49 bytes
Experimente online!
Como funciona
A triangularidade exige que o código tenha uma distribuição triangular dos pontos. Ou seja, o comprimento de cada linha deve ser igual ao número de linhas multiplicado por 2 e decrementado, e cada linha deve ter (em cada lado) um número de pontos igual à sua posição no programa (a linha inferior é a linha 0, o acima é a linha 1 e assim por diante). Existem apenas alguns comandos, e qualquer caractere que não seja o listado na página 'Wiki / Comandos' é tratado como não operacional (pontos estranhos não afetam o programa de forma alguma, desde que a forma geral do programa permanece retangular).
Note-se que para os comandos de dois argumentos, eu usei um e b em todo o explicação. Tendo isso em mente, vamos ver o que o programa real faz, depois de remover todos os caracteres estranhos que compõem o preenchimento:
Uma solução alternativa e mais curta se o preenchimento não for necessário:
Experimente online!
fonte
PowerShell 3.0, 45 bytes
A chamada matemática doeu e o arredondamento dos banqueiros do PS é o diabo real (portanto, é necessário que o regex trunque para salvar um byte), mas isso parece bem.
fonte
Java (JDK) , 28 bytes
Experimente online!
Como o exemplo realmente não foi muito bom: p
Créditos
fonte
Geléia , 7 bytes
Executa aproximadamente no tempo O (2 n ) .
Experimente online!
Como funciona
fonte
JavaScript (ES7),
2219 bytes-3 bytes graças a ETHproductions.
Tente
Explicação
Multiplique a entrada por 8 e adicione 1, aumente para 0,5, fornecendo a raiz quadrada, subtraia 1 e mude o resultado para 1.
fonte
n=>(8*n+1)**.5-1>>1
salvar 3 bytes? (não testei)Python 2/3, 32 bytes
Implementação em Python da fórmula de formulário fechado
A divisão inteira
//2
arredonda para zero, portanto, não éfloor( )
necessáriofonte
from math import sqrt
funcionar? Nesse caso, ele deve ser incluído no bytecount. (Nesse caso,lambda n:int((math.sqrt(1+8*n)-1)//2) import math
é um pouco mais curto. )Haskell , 28 bytes
Meio chato, mas
é bem mais curto que a outra solução Haskell etem uma ótima expressão sem pontos. Infelizmente, não consegui reduzi-lo mais sem o sistema de tipos atrapalhar:Experimente online!
Sem ponto, 33 bytes
Como alternativa, 33 bytes
Mesmo tamanho que a versão pointfree, mas muito mais interessante.
fonte
Via Láctea , 12 bytes
Explicação
fonte
Pyt ,
75 bytesExplicação:
Maneira mais rápida, mas mais longa
Pyt ,
119 bytesExplicação:
Caminho alternativo - porto da resposta de Shaggy
Pyt ,
87 bytesfonte
J , 11 bytes
Experimente online!
fonte
*
para produzir 1Espaço em branco , 111 bytes
Letras
S
(espaço),T
(tabulação) eN
(nova linha) adicionadas apenas como destaque.[..._some_action]
adicionado apenas como explicação.Experimente online (apenas com espaços brutos, guias e novas linhas).
Explicação em pseudo-código:
Usa a fórmula:
OBSERVAÇÃO: O espaço em branco não possui uma raiz quadrada incorporada, portanto, precisamos fazer isso manualmente.
fonte
Vitsy , 16 bytes
Experimente online!
Também poderia adicionar minha própria contribuição à mistura. Isso é mais curto que a solução de iterações de partição no Vitsy.
fonte
Oásis , 14 bytes
Experimente online!
Quão?
Esta é uma solução recursiva que incrementa o resultado quando encontra um índice triangular, começando com 0 para a entrada 0.
fonte
Perl 5
-p
, 19 (++) bytesExperimente online!
fonte
Ruby , 27 bytes
Três pelo preço de um. Estou decepcionado por não poder ir mais baixo.
Experimente online! (para selecionar a função, adicione f = na frente)
fonte