Desafío
Imaginemos una N
tupla de enteros entre 0 e M
inclusive, y llamémoslo F
.
Hay (M + 1) ** N
posibles F
s en total.
¿Cuántos F
s satisfacen todas las siguientes desigualdades (el índice se basa en uno)?
F[n] + F[n+1] <= M
para1 <= n < N
F[N] + F[1] <= M
Escribir un programa o función que toma dos números enteros positivos N
y M
y envía la respuesta en cualquier forma conveniente.
Casos de prueba
(N,M) => Answer
(1,1) => 1
(2,1) => 3
(3,1) => 4
(4,1) => 7
(1,2) => 2
(2,2) => 6
(3,2) => 11
(4,2) => 26
(10,3) => 39175
(10,4) => 286555
(10,5) => 1508401
(25,3) => 303734663372
(25,4) => 43953707972058
(25,5) => 2794276977562073
(100,3) => 8510938110502117856062697655362747468175263710
(100,4) => 3732347514675901732382391725971022481763004479674972370
(100,5) => 60964611448369808046336702581873778457326750953325742021695001
Explicación
M (max value of element) = 1
F[1] + F[1] <= 1; F = [0]
(1,1) => 1
F[1] + F[2] <= 1; F = [0,0], [0,1], [1,0]
(2,1) => 3
F = [0,0,0], [0,0,1], [0,1,0], [1,0,0]
(3,1) => 4
F = [0,0,0,0], [0,0,0,1], [0,0,1,0], [0,1,0,0], [0,1,0,1], [1,0,0,0], [1,0,1,0]
(4,1) => 7
---
M = 2
F[1] + F[1] <= 2; F = [0], [1]
(1,2) => 2
F = [0,0], [0,1], [0,2], [1,0], [1,1], [2,0]
(2,2) => 6
F = [0,0,0], [0,0,1], [0,0,2], [0,1,0], [0,1,1], [0,2,0], [1,0,0], [1,0,1],
[1,1,0], [1,1,1], [2,0,0]
(3,2) => 11
(4,2) => 26 (left as exercise for you)
Reglas
- Este es un desafío de complejidad restringida . La complejidad temporal de su código debe ser polinómica
M
yN
(por ejemplo, no puede generar todas las(M + 1) ** N
tuplas y luego verificar la condición). Explique su enfoque en su presentación. - Se aplican reglas estándar de código de golf . La respuesta más corta en bytes gana.
code-golf
restricted-complexity
Bubbler
fuente
fuente
mat(...,int)
no parece funcionar para losn=100
casos. El método es correcto (el uso de sympy para sumar los poderes de las raíces del polinomio característico funciona, por ejemplo), pero numpy falla en algún lugar a medida que aumentan los números (¿tal vez es el**
operador de poder?)Pyth , 27 bytes
Demostración
Espera entrada en el formato:
Esta es una programación dinámica clásica, sobre el extremo izquierdo de los valores establecidos hasta ahora, el extremo derecho y el tamaño actual de la brecha.
Cómo funciona, en pseudocódigo / Python:
Q
se usa paraM
,z
se usa paraN
,:
esfill
,N
esleft
,T
esright
,Y
esgap
.fuente
MATL ,
1312 bytesPruébalo en línea! Esta es una traducción directa de la respuesta de Python de xnor y mi primera respuesta MATL, por lo que probablemente no sea óptima. Por ejemplo, es probable que haya una forma más corta de obtener una matriz triangular superior izquierda de unos que
t&lYRP
. Editar: Y resulta que hay, a saber:&>~P
. ¡Gracias a Luis Mendo por -1 byte!fuente
Stax , 17 bytes
Ejecutar y depurarlo
Desempaquetado, sin golf y comentado, se ve así.
Ejecute este
fuente
R , 72 bytes
Pruébalo en línea!
Puertos xnor enfoque.
Falla para casos de prueba más grandes ya que R solo tiene soporte entero de 32 bits (se convierten a
double
una vez que se alcanza el valor int máximo), por lo quegmp
lo que sería necesario u otra biblioteca aritmética de precisión arbitraria.Curiosamente, R carece de un operador de potencia de matriz, como
^
siempre se aplica por elementos.fuente
%^%
operador implementado correctamente en el paqueteexpm
que permitiría -5 bytes , pero desafortunadamente, no está disponible en TIO (tuve que probarlo localmente).function(M,N)sum(diag(expm::`%^%`(outer(0:M,0:M,"+")<=M,N)))