As videiras olímpicas realizam suas rotinas em árvores comuns. Em particular, a Árvore Padrão npossui vértices para 0cima n-1e arestas que vinculam cada vértice diferente de zero aao vértice n % aabaixo dele. Então, por exemplo, a Árvore Padrão 5 se parece com isso:
3
|
2 4
\ /
1
|
0
porque o restante quando 5 é dividido por 3 é 2, o restante quando 5 é dividido por 2 ou por 4 é 1 e o restante quando 5 é dividido por 1 é 0.
Este ano, Tarzan estará defendendo seu ouro com novas rotinas, cada uma das quais começa no vértice n - 1, oscila para o vértice n - 2, continua para o vértice n - 3etc., até que finalmente desmonte para o vértice 0.
A pontuação de uma rotina é a soma das pontuações de cada giro (incluindo a desmontagem), e a pontuação de um giro é a distância dentro da árvore entre seus pontos inicial e final. Assim, a rotina de Tarzan na Árvore Padrão 5 tem uma pontuação de 6:
- um balanço de
4para3marcar três pontos (baixo, cima, cima), - um balanço de
3para2marcar um ponto (para baixo), - um balanço de
2para1marcar um ponto (para baixo), e - uma desmontagem de
1para0marcar um ponto (para baixo).
Escreva um programa ou função que, dado um número inteiro positivo n, calcule a pontuação da rotina de Tarzan na Árvore Padrão n. Entradas e saídas de amostra:
1 -> 0
2 -> 1
3 -> 2
4 -> 6
5 -> 6
6 -> 12
7 -> 12
8 -> 18
9 -> 22
10 -> 32
11 -> 24
12 -> 34
13 -> 34
14 -> 36
15 -> 44
16 -> 58
17 -> 50
18 -> 64
19 -> 60
20 -> 66
21 -> 78
22 -> 88
23 -> 68
24 -> 82
Regras e pontuação de código são como de costume para o código-golfe .
fonte
Respostas:
C,
98bytesIsso calcula a distância entre cada par de pontos com a seguinte fórmula:
Isso tem a vantagem de que, quando aplicado a todos os pares, é o mesmo que:
Para tornar a lógica mais simples, assumimos que estamos passando do nó 0 para o nó n-1, em vez de n-1 para 0, conforme a pergunta. A distância do nó raiz ao nó 0 é obviamente 0 (são iguais). E podemos ver que, para a maioria das árvores, a distância entre o último nó e a raiz é 2:
Isso significa que temos alguns casos especiais (n <2), mas podemos explicá-los com bastante facilidade.
Demolir:
Obrigado @feersum por 1 byte salvo
Bônus: Árvores!
Eu escrevi um programa rápido e sujo para ver como são essas árvores. Aqui estão alguns dos resultados:
19:
fonte
Python 2, 85 bytes
fonte
Perl,
65595554 bytesInclui +2 para
-apExecute com o tamanho da árvore no STDIN:
vines.pl:Explicação
Se você reescrever a árvore
para aquele em que cada nó contém o conjunto de todos os seus ancestrais e ele próprio:
Então, podemos descrever, por exemplo, todos os nós do caminho de 4 a 3 como:
O número de arestas é um a menos que o número de nós; portanto, podemos usá-lo para ignorar o ponto de junção; portanto, o número de arestas no caminho de 4 a 3 é 3 porque:
Observe que isso também funciona para um caminho que desce diretamente para o seu destino, por exemplo, para o caminho de 3 a 2, o número de arestas é 1 porque:
Podemos então somar todas essas combinações.
Se você olhar apenas para um nó, por exemplo, nó 2 com conjunto de ancestrais
{2,3}. Este nó contribuirá uma vez ao processar o caminho2 to 1porque contém um 2, mas não um 1. Ele não contribuirá com nada para o caminho,3 to 2pois possui 2 e 3, mas contribuirá uma vez ao processar o caminho . O Simular 0 é unilateral, mas como 0 está sempre na raiz da árvore e contém todos os números (é a junção final e não contamos junções), nunca há contribuição de 0, portanto é mais fácil deixar o nó 0 completamente.4 to 3pois possui 3, mas não 4. Em geral, um número no conjunto ancestral de um nó contribuirá com um para cada vizinho (um menor ou mais alto) que não esteja no conjunto. Exceto pelo elemento máximo (4 neste caso), que apenas contribui para o vizinho baixo 3, pois não há caminho5 to 4Portanto, também podemos resolver o problema observando o conjunto de ancestrais de cada nó, contar as contribuições e somar todos os nós.
Para processar vizinhos facilmente, vou representar os conjuntos de ancestrais como uma sequência de espaços e 1's, onde cada 1 na posição p representa que n-1-p é um ancestral. Então, por exemplo, no nosso caso de
n=51 na posição 0, indica 4 é um ancestral. Vou deixar espaços à direita. Portanto, a representação real da árvore que construirei é:Observe que eu deixei de fora o nó 0, que seria representado por,
"11111"porque eu vou ignorar o nó 0 (ele nunca contribui).Antepassados sem vizinho inferior agora são representados no final de uma sequência de 1s. Antepassados sem vizinho mais alto agora são representados pelo início de uma sequência de 1s, mas devemos ignorar qualquer início de uma sequência no início de uma sequência, pois isso representaria o caminho
5 to 4que não existe. Essa combinação é exatamente correspondida pelo regex/.\b/.A construção das seqüências ancestrais é feita processando todos os nós na ordem
n-1 .. 1e, em seguida, defina 1 na posição do próprio nó e fazendo um "ou" no descendente.Com tudo isso, o programa é fácil de entender:
Observe que a substituição
/.\b/por/\b/resolve a versão de ida e volta desse problema em que o tarzan também segue o caminho0 to n-1Alguns exemplos de como as seqüências de caracteres ancestrais são exibidas (em ordem
n-1 .. 1):fonte
Mathematica,
113103102 bytes-10 bytes graças a @feersum; -1 byte graças a @MartinEnder
O seguinte é muito mais rápido (mas mais longo, infelizmente, com 158 bytes ):
fonte
With. Além disso, parece que toda vez queRangeé usado,aé o argumento, para que possa ser fatorado.r=Range[a=#-1]salva um byte.J, 37 bytes
Uso:
Experimente online aqui.
fonte
JavaScript (ES6),
118116 bytesA falta de uma função de diferença definida realmente dói, mas alguma recursão criativa reduz um pouco a contagem de bytes. Editar: salvou 2 bytes removendo um parâmetro desnecessário.
fonte