Considere un triángulo ABC donde cada lado tiene una longitud entera (un triángulo integral ). Defina una mediana de ABC como un segmento de línea desde un vértice hasta el punto medio del lado opuesto. En la figura siguiente, los segmentos de línea roja representan las medianas. Tenga en cuenta que cualquier triángulo tiene tres medianas.
Sea n un número entero positivo. ¿Cuántos triángulos integrales no degenerados con una longitud de lado menor o igual a n tienen al menos una mediana integral?
Desafío
Escriba un programa para calcular el número de triángulos integrales con al menos una mediana integral para una longitud lateral máxima dada n . El orden de las longitudes de los lados no importa, es decir, <6,6,5> representa el mismo triángulo que <5,6,6> y debe contarse solo una vez. Excluya triángulos degenerados como <1,2,3>.
Puntuación
La n más grande para la cual su programa puede generar el número de triángulos en 60 segundos en mi máquina es su puntaje. El programa con la puntuación más alta gana. Mi máquina es una Sony Vaio SVF14A16CLB, Intel Core i5, 8GB de RAM.
Ejemplos
Deje T ( N ) sea el programa con entrada de N .
T(1) = 0
T(6) = 1
T(20) = 27
T(22) = 34
Tenga en cuenta que T (1) = T (2) = T (3) = T (4) = T (5) = 0 porque ninguna combinación de lados integrales producirá una mediana integral. Sin embargo, una vez que llegamos a 6, podemos ver que una de las medianas del triángulo <5,5,6> es 4, entonces T (6) = 1.
Tenga en cuenta también que T (22) es el primer valor en el que el doble conteo se convierte en un problema: el triángulo <16,18,22> tiene las medianas 13 y 17 (y 2sqrt (85)).
Computando las medianas
Las medianas de un triángulo se pueden calcular mediante las siguientes fórmulas:
Current top score: Sp3000 - 7000 points - C
fuente
Respuestas:
C, fuerza bruta - n = 6080
Esto es más una línea de base que un contendiente serio, pero al menos debería comenzar las cosas.
n = 6080 es lo más alto que obtuve en un minuto de tiempo de ejecución en mi propia máquina, que es una MacBook Pro con un Intel Core i5. El resultado que obtuve para este valor es:
El código es puramente fuerza bruta. Enumera todos los triángulos dentro del límite de tamaño y prueba la condición:
fuente
lrintf()
o en(int)roundf()
lugar de agregar 0.5f y usar el truncamiento predeterminado. Sin-ffast-math
embargo, a veces es necesario utilizarlo para compilarlo en una solacvtss2si
instrucción. gcc en línealrintf()
ysqrtf
con solo-fno-math-errno
, para que obtenga asm eficiente: godbolt.org/g/E3hncQ . (Solía-march=ivybridge
porque esa es la CPU del OP). Con-ffast-math
, clang convierte el sqrt en una iteración rsqrt + Newton; IDK si eso es una victoria.roundf
. Use(int)nearbyintf()
iflrintf()
no está en línea, porque usa el modo de redondeo actual en lugar de uno extraño específico. stackoverflow.com/questions/37620659/…C, aproximadamente
66506900Realmente no uso C a menudo, pero con la cantidad de aritmética, parecía una buena opción de lenguaje. El algoritmo central es la fuerza bruta como la respuesta de @ RetoKoradi , pero con algunas optimizaciones simples. Sin embargo, no estoy seguro de que nuestros valores sean comparables, porque la computadora de @ RetoKoradi parece ser más rápida que la mía.
La mayor optimización es pasar
% 4
completamente por alto el cheque. Un cuadrado enteron*n
es 0 o 1 módulo 4, dependiendo de sin
es 0 o 1 módulo 2. Por lo tanto, podemos ver todas las posibilidades para(x, y, z) % 2
:Convenientemente, solo hay dos casos a considerar:
(0, 0, 0)
y(1, 1, 0)
que, dados los primeros dos ladosa, b
, equivale a que el tercer ladoc
tenga paridada^b
:a^b
es la misma paridad quea-b
, así que en lugar de buscarc = a-b+1
y subir por 1s, esto nos permite buscarc = a-b+2
y subir por 2s.Otra optimización proviene del hecho de que, para el
(1, 1, 0)
caso, solo necesitamos llamar a is_square una vez ya que solo funciona una permutación. Este es un caso especial en el código desenrollando la búsqueda.La otra optimización incluida es simplemente un fallo rápido en la
is_square
función.La compilación se realizó con
-std=c99 -O3
.(Gracias a @RetoKoradi por señalar que
0.5
in is_square debía ser0.5f
para evitar una doble conversión).fuente
0.5f
lugar de0.5
enis_square()
.0.5
es una constante de tipodouble
, por lo que la expresión producirá un valor doble cuando agregue0.5
, incluida la conversión de tipo defloat
adouble
para el otro término.f
, en realidad.Felix, desconocido
Básicamente un puerto de la respuesta C, pero es más rápido que él, probado con
clang -O3
yicc -O3
. Felix y Nim son literalmente los únicos dos lenguajes que conozco que pueden vencer a C y C ++ en los puntos de referencia. Estoy trabajando en una versión paralela, pero será un poco hasta que esté terminado, así que decidí publicar esto más adelante.También pongo "desconocido" porque mi computadora no es necesariamente la más rápida del mundo ...
Comando utilizado para construir:
El C ++ generado es bastante interesante de ver:
fuente
C # (¿aproximadamente 11000?)
n
se toma como un argumento de línea de comandos.Explicación
fuente
n=5000
son 67 segundos para la respuesta de Reto Koradi, 48 segundos para la respuesta de Sp3000 y 13 segundos para mi respuesta.C, n = 3030 aquí
resultados:
el código anterior sería la traducción en C de la respuesta de Axiom (si no contamos la función isq ()).
Mi compilador no vincula una función que otros usan sqrtf () ... aquí no hay una función sqrt para flotante ... ¿Están seguros de que sqrtf es una función estándar de C?
fuente
NARS APL, n =
239282 en 59 segundos(traduzco la respuesta Axiom one, en APL) prueba:
fuente
Axioma, n = 269 en 59 segundos
Si a, b, cx son la longitud de los lados de un triángulo del lado de longitud máxima n ...
Sabríamos que m: = sqrt ((2 * (a ^ 2 + b ^ 2) -cx ^ 2) / 4)
Como Peter Taylor había dicho, 4 | (2 * (a ^ 2 + b ^ 2) -cx ^ 2) y porque 2 | 2 * (a ^ 2 + b ^ 2) que 2 | cx ^ 2 => cx = 2 * c. Entonces de 1 será
a, yb tiene que tener la misma paridad, por lo que podríamos escribir b en función de a
que tenemos eso
para que el (1) pueda ser reescrito ver (2) (3) (4) como:
dónde
resultados
fuente
¡VBA 15,000 en DIEZ segundos!
Esperaba mucho menos después de estas otras publicaciones. En un Intel 7 con 16 GB de RAM, obtengo 13-15,000 en DIEZ segundos. En un Pentium con 4 GB de RAM, obtengo 5-7,000 en DIEZ segundos. El código está abajo. Aquí está el último resultado en el Pentium
Se levantó hasta un triángulo con lados 240, 239, 31 y un medio de 121. El recuento de medios es 7,371.
fuente