Antecedentes

La moneda oficial de la nación imaginaria de Golfenistán es el foo , y solo hay tres tipos de monedas en circulación: 3 foos, 7 foos y 8 foos. Uno puede ver que no es posible pagar ciertas cantidades, como 4 foos, usando estas monedas. Sin embargo, se pueden formar todas las cantidades suficientemente grandes. Su trabajo es encontrar la mayor cantidad que no se puede formar con las monedas (5 foos en este caso), lo que se conoce como el problema de la moneda .

Entrada

Su entrada es una lista de enteros positivos, que representan los valores de las monedas en circulación. Hay dos cosas garantizadas al respecto:L = [n1, n2, ..., nk]

• El MCD de los elementos de Les 1.
• L no contiene el número 1.

Puede estar sin clasificar y / o contener duplicados (piense en monedas de edición especial).

Salida

Como el MCD de Les 1, cada entero lo suficientemente grande mpuede expresarse como una combinación lineal no negativa de sus elementos; en otras palabras, tenemos

 m = a1*n1 + a2*n2 + ... + ak*nk 

para algunos números enteros . Su salida es el entero más grande que no se puede expresar de esta forma. Como pista, se sabe que la salida siempre es menor que , si y son los elementos máximos y mínimos de ( referencia ).ai ≥ 0(n1 - 1)*(nk - 1)n1nkL

Reglas

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten. Si su idioma tiene una operación incorporada para esto, no puede usarlo. No hay requisitos de tiempo o eficiencia de memoria, excepto que debe poder evaluar los casos de prueba antes de publicar su respuesta.

Después de publicar este desafío, el usuario @vihan señaló que Stack Overflow tiene un duplicado exacto . Basado en esta discusión Meta , este desafío no se eliminará como un duplicado; sin embargo, pido que todas las respuestas basadas en las de la versión SO deben citar los originales, recibir el estado de Wiki de la comunidad y eliminarse si el autor original desea publicar su respuesta aquí.

Casos de prueba

[3, 7, 8] -> 5
[25, 10, 16] -> 79
[11, 12, 13, 14, 13, 14] -> 43
[101, 10] -> 899
[101, 10, 899] -> 889
[101, 10, 11] -> 89
[30, 105, 70, 42] -> 383
[2, 51, 6] -> 49

Pyth, 23 bytes

ef!fqTs.b*NYQY^UTlQS*FQ

Es muy lento, ya que verifica todos los valores hasta el producto de todas las monedas. Aquí hay una versión que es casi idéntica, pero 1) reduce el conjunto de monedas a las que no son divisibles entre sí y 2) solo verifica valores de hasta (max(coins) - 1) * (min(coins) - 1)(47 bytes):

=Qu?.A<LiHdG+GHGQYef!fqTs.b*NYQY^UTlQS*thSQteSQ

Explicación

                   S            range 1 to
                    *FQ         product of input
 f                             filter by
               UT                range 0 to T 
              ^  lQ              cartesian power by number of coins
   f                            filter by
      s.b*NYQY                   sum of coin values * amounts
    qT                           equals desired number T
  !                             nothing matching that filter
e                             take last (highest) element

Perl 60 54 51 bytes

Código de 50 bytes + línea de comando de 1 bytes

$.*=$_,$r.=1x$_."|"}{$_=$.while(1x$.--)=~/^($r)+$/

Seguirá jugando al golf y publicará una explicación más tarde. El enfoque básico es dejar que el motor regex haga el trabajo duro con la coincidencia de cadenas. Por ejemplo, construirá una expresión regular similar a^(.{3})*(.{7})*(.{8})*$ y coincidirá con una cadena de longitud ndonde ndesciende del producto de las entradas hasta que no coincida.

Tenga en cuenta que esto se volverá exponencialmente lento a medida que aumente el número de argumentos.

Uso: los argumentos se leen desde STDIN (nueva línea separada), por ejemplo:

printf "101\n10" | perl -p entry.pl

R , 84 78 bytes

$a_1, a_2,\ldots$

a=scan();max((1:(b<-min(a)*max(a)))[-colSums(combn(outer(a,0:b),sum(!!a)))])

Pruébalo en línea!

$a_i$outer sin "*" y en colSumslugar de "aplicar (..., 2, suma)".

Una versión más rápida pero más larga (por dos bytes) solo considera max(a):

a=scan();max((1:(min(a)*(b<-max(a))))[-apply(combn(outer(a,0:b,"*"),sum(!!a)),2,sum)])

Una versión un poco más corta (78 bytes) que con frecuencia requiere demasiado registro o demasiado espacio para ejecutarse. Pruébelo en línea es

a=scan();max((1:(b<-prod(a)))[-apply(combn(outer(a,0:b,"*"),sum(!!a)),2,sum)])

Python2, 188 187 bytes

def g(L):
 M=max(L);i=r=0;s=[0]*M;l=[1]+s[1:]
 while 1:
    if any(all((l+l)[o:o+min(L)])for o in range(M)):return~-s[r]*M+r
    if any(l[(i-a)%M]for a in L):l[i]=1
    else:r=i
    s[i]+=1;i=(i+1)%M

La segunda sangría se representa como 4 espacios en SO, que deberían ser pestañas.

En realidad, una solución "rápida", no fuerza bruta, utiliza el "Método de Wilf" como se describe aquí .

Javascript ES6, 120 130 126 128 127 125 caracteres

f=a=>`${r=[1|a.sort((a,b)=>a-b)]}`.repeat(a[0]*a[a.length-1]).replace(/./g,(x,q)=>r[q]|a.map(x=>r[q+x]|=r[q])).lastIndexOf(0)

Versión alternativa de 126 caracteres:

f=a=>{r=[1];a.sort((a,b)=>a-b);for(q=0;q<a[0]*a[a.length-1];++q)r[q]?a.map(x=>r[q+x]=1):r[q]=0;return r.join``.lastIndexOf(0)}

Prueba:

"[3, 7, 8] -> 5\n\
[25, 10, 16] -> 79\n\
[11, 12, 13, 14, 13, 14] -> 43\n\
[101, 10] -> 899\n\
[101, 10, 899] -> 889\n\
[101, 10, 11] -> 89\n\
[30, 105, 70, 42] -> 383\n\
[2, 51, 6] -> 49".replace(/(\[.*?\]) -> (\d+)/g, function (m, t, r) {
  return f(JSON.parse(t)) == r
})