fundo
Uma sequência de conjuntos ex-crescente da ordem é definida como uma sequência de conjuntos inteiros que satisfaz o seguinte:S 1 , S 2 , ⋯ , S n
- Cada é um subconjunto não vazio de . { 1 , 2 , ⋯ , N }
- Para , , ou seja, quaisquer dois conjuntos consecutivos não têm elementos em comum.S i ∩ S i + 1 = ∅
- Para , a média (valor médio) de é estritamente menor que a de .S i S i + 1
Desafio
Dado um número inteiro positivo N
, produza o comprimento da sequência de ordem mais longa ex-crescente N
.
Casos de teste
Estes são baseados nos resultados por usuário do Project Euler thundre .
1 => 1 // {1}
2 => 2 // {1} {2}
3 => 3 // {1} {2} {3}
4 => 5 // {1} {2} {1,4} {3} {4}
5 => 7 // {1} {2} {1,4} {3} {2,5} {4} {5}
6 => 10 // {1} {2} {1,4} {3} {1,4,5} {2,3,6} {4} {3,6} {5} {6}
7 => 15 // {1} {2} {1,4} {3} {1,2,7} {3,4} {1,2,5,7} {4} {1,3,6,7} {4,5} {1,6,7} {5} {4,7} {6} {7}
8 => 21
9 => 29
10 => 39
11 => 49
12 => 63
13 => 79
14 => 99
15 => 121
16 => 145
17 => 171
18 => 203
19 => 237
20 => 277
21 => 321
22 => 369
23 => 419
24 => 477
25 => 537
Regras
Aplicam-se as regras de código-golfe padrão . O menor envio válido em bytes vence.
Recompensa
Esse problema foi discutido aqui no fórum do Project Euler há cerca de 4 anos, mas não conseguimos criar um algoritmo de tempo polinomial comprovável (em termos de N
). Portanto, concederei +200 de recompensa à primeira submissão que conseguir isso ou provar sua impossibilidade.
Respostas:
Braquilog , 28 bytes
Experimente online!
Isso é realmente muito lento. Demora cerca de 30 segundos por
N = 3
e não foi concluído após 12 minutosN = 4
.Explicação
Versão mais rápida, 39 bytes
Isso leva cerca de 50 segundos no meu computador para
N = 4
.Este é o mesmo programa, exceto que classificamos o subconjunto de subconjuntos pela média em vez de fazer uma permutação aleatória. Então usamos em
{⟨+/l⟩/₁/₁}ᵒ
vez dep
.Precisamos obter uma média flutuante porque acabei de descobrir um bug ridículo no qual flutuadores e números inteiros não se comparam por valor, mas por tipo com predicados de ordenação (é também por isso que eu uso
<ᵈ
e não<₁
para comparar as duas médias; o último exigiria que truque de dupla inversão para o trabalho).fonte
CJam (81 bytes)
Demonstração online . Ele deve ser executado para entrada
4
em um tempo razoável, mas eu não tentaria com entradas mais altas.Dissecação
fonte
JavaScript (ES6), 175 bytes
Uma pesquisa recursiva ingênua e bastante lenta. Demora cerca de 15 segundos para calcular os 7 primeiros termos no TIO.
Experimente online!
ou teste esta versão modificada que gera a sequência de conjuntos mais longa e ex-crescente.
Quão?
Parte recursiva:
fonte
Python 3 ,
205197184182 bytesoitovinte e um bytes graças a ovs .Experimente online!
fonte
sum
vez dechain.from_iterable
.