Los swingers olímpicos realizan sus rutinas en árboles estándar. En particular, el Árbol estándar ntiene vértices para 0arriba n-1y bordes que unen cada vértice distinto de cero acon el vértice n % adebajo de él. Entonces, por ejemplo, Standard Tree 5 se ve así:
3
|
2 4
\ /
1
|
0
porque el resto cuando 5 se divide por 3 es 2, el resto cuando 5 se divide por 2 o por 4 es 1, y el resto cuando 5 se divide por 1 es 0.
Este año, Tarzán defenderá su oro con nuevas rutinas, cada una de las cuales comienza en el vértice n - 1, cambia al vértice n - 2, continúa al vértice n - 3, etc., hasta que finalmente desmonta al vértice 0.
El puntaje para una rutina es la suma de los puntajes para cada swing (incluido el desmontaje), y el puntaje para un swing es la distancia dentro del árbol entre sus puntos de inicio y final. Por lo tanto, la rutina de Tarzán en Standard Tree 5 tiene una puntuación de 6:
- un swing de
4a3anota tres puntos (abajo, arriba, arriba), - un swing de
3a2anota un punto (abajo), - un swing de
2a1anota un punto (abajo), y - un desmontaje de
1a0anota un punto (abajo).
Escriba un programa o función que, dado un número entero positivo n, calcule el puntaje de la rutina de Tarzán en el Árbol estándar n. Muestra de entradas y salidas:
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
Las reglas y la puntuación de código son las habituales para code-golf .
fuente
Respuestas:
C,
9897 bytesEsto calcula la distancia entre cada par de puntos con la siguiente fórmula:
Esto tiene la ventaja de que cuando se aplica a todos los pares, es lo mismo que:
Para simplificar la lógica, asumimos que vamos del nodo 0 al nodo n-1, en lugar de n-1 a 0 como dice la pregunta. La distancia desde el nodo raíz al nodo 0 es obviamente 0 (son lo mismo). Y podemos ver que para (la mayoría) de los árboles, la distancia desde el último nodo hasta la raíz es 2:
Esto significa que tenemos algunos casos especiales (n <2) pero podemos dar cuenta de ellos con bastante facilidad.
Descompostura:
Gracias @feersum por 1 byte guardado
Bonus: ¡Árboles!
Escribí un programa rápido y sucio para ver cómo se ven estos árboles. Estos son algunos de los resultados:
19:
fuente
Python 2, 85 bytes
fuente
Perl,
65595554 bytesIncluye +2 para
-apEjecutar con el tamaño del árbol en STDIN:
vines.pl:Explicación
Si reescribes el árbol
a uno donde cada nodo contiene el conjunto de todos sus antepasados y a sí mismo:
Luego podemos describir, por ejemplo, todos los nodos, la ruta de 4 a 3 como:
El número de bordes es uno menos que el número de nodos, por lo que podemos usarlo para ignorar el punto de unión, por lo que el número de bordes en la ruta de 4 a 3 es 3 porque:
Tenga en cuenta que esto también funciona para una ruta que desciende directamente a su objetivo, por ejemplo, para la ruta de 3 a 2, el número de bordes es 1 porque:
Entonces podemos sumar todas estas combinaciones.
Si, en cambio, observa solo un nodo, por ejemplo, el nodo 2 con el conjunto ancestro
{2,3}. Este nodo contribuirá una vez cuando procese la ruta2 to 1porque contiene un 2 pero no un 1. No aportará nada para la ruta3 to 2ya que tiene 2 y 3, pero contribuirá una vez cuando procese la ruta4 to 3ya que tiene 3 pero no 4. En general, un número en el conjunto ancestro de un nodo contribuirá con uno para cada vecino (uno más bajo o más alto) que no esté en el conjunto. Excepto por el elemento máximo (4 en este caso) que solo contribuye para el vecino bajo 3 ya que no hay ruta5 to 4. El 0 simular es unilateral, pero dado que 0 siempre está en la raíz del árbol y contiene todos los números (es la unión final y no contamos las uniones), nunca hay ninguna contribución de 0, por lo que es más fácil dejar el nodo 0 fuera por completo.Por lo tanto, también podemos resolver el problema mirando el conjunto de antepasados para cada nodo, contar las contribuciones y sumar sobre todos los nodos.
Para procesar fácilmente a los vecinos, voy a representar los conjuntos de antepasados como una cadena de espacios y 1 donde cada 1 en la posición p representa que n-1-p es un antepasado. Entonces, por ejemplo, en nuestro caso de
n=5un 1 en la posición 0 indica que 4 es un antepasado. Dejaré los espacios finales. Entonces, la representación real del árbol que construiré es:Observe que omití el nodo 0, que estaría representado por
"11111"porque voy a ignorar el nodo 0 (nunca contribuye).Los antepasados sin vecino inferior ahora están representados por el final de una secuencia de 1. Los antepasados sin vecino superior ahora están representados por el inicio de una secuencia de 1, pero deberíamos ignorar cualquier inicio de una secuencia al comienzo de una cadena ya que esto representaría la ruta
5 to 4que no existe. Esta combinación coincide exactamente con la expresión regular/.\b/.La construcción de las cadenas ancestrales se realiza procesando todos los nodos en el orden
n-1 .. 1y establece un 1 en la posición del nodo en sí y haciendo un "o" en el descendiente.Con todo eso, el programa es lo suficientemente fácil de entender:
Observe que reemplazar
/.\b/por/\b/resuelve la versión de ida y vuelta de este problema donde tarzan también toma el camino0 to n-1Algunos ejemplos de cómo se ven las cadenas ancestrales (dadas en orden
n-1 .. 1):fuente
Mathematica,
113103102 bytes-10 bytes gracias a @feersum; -1 byte gracias a @MartinEnder
Lo siguiente es mucho más rápido (pero más largo, desafortunadamente, en 158 bytes ):
fuente
With. También parece que cada vez queRangese usa,aes el argumento, por lo que podría factorizarse.r=Range[a=#-1]guarda un byte.J, 37 bytes
Uso:
Pruébelo en línea aquí.
fuente
JavaScript (ES6),
118116bytesLa falta de una función de diferencia establecida realmente duele, pero cierta recursividad creativa reduce un poco el recuento de bytes. Editar: se guardaron 2 bytes eliminando un parámetro innecesario.
fuente