fundo

A moeda oficial da nação imaginária do Golfenistão é o foo , e existem apenas três tipos de moedas em circulação: 3 foos, 7 foos e 8 foos. Pode-se ver que não é possível pagar certas quantias, como 4 foos, usando essas moedas. No entanto, todas as quantidades grandes o suficiente podem ser formadas. Seu trabalho é encontrar a maior quantidade que não pode ser formada com as moedas (neste caso, 5 foos), conhecida como problema das moedas .

Entrada

Sua entrada é uma lista de números inteiros positivos, representando os valores das moedas em circulação. Duas coisas são garantidas:L = [n1, n2, ..., nk]

• O MDC dos elementos de Lé 1.
• L não contém o número 1.

Pode ser não classificado e / ou conter duplicatas (pense em moedas de edição especial).

Resultado

Como o GCD de Lé 1, todo número inteiro grande o suficiente mpode ser expresso como uma combinação linear não negativa de seus elementos; em outras palavras, temos

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

para alguns números inteiros . Sua saída é o maior número inteiro que não pode ser expresso neste formulário. Como sugestão, sabe-se que a saída é sempre menor que , se e são os elementos máximo e mínimo de ( referência ).ai ≥ 0(n1 - 1)*(nk - 1)n1nkL

Regras

Você pode escrever um programa completo ou uma função. A menor contagem de bytes vence e as brechas padrão não são permitidas. Se seu idioma possui uma operação interna para isso, você não pode usá-lo. Não há requisitos para eficiência de tempo ou memória, exceto que você deve poder avaliar os casos de teste antes de postar sua resposta.

Depois de postar esse desafio, o usuário @vihan apontou que o Stack Overflow tem uma duplicata exata . Com base nessa discussão meta , esse desafio não será excluído como duplicado; no entanto, peço que todas as respostas baseadas na versão SO citem os originais, recebam o status do Wiki da Comunidade e sejam excluídas se o autor original desejar postar sua resposta aqui.

Casos de teste

[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

Pitão, 23 bytes

ef!fqTs.b*NYQY^UTlQS*FQ

É muito lento, pois verifica todos os valores até o produto de todas as moedas. Aqui está uma versão quase idêntica, mas 1) reduz o conjunto de moedas para as que não são divisíveis uma pela outra e 2) apenas verifica valores até (max(coins) - 1) * (min(coins) - 1)(47 bytes):

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

Explicação

                   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 + linha de comando de 1 bytes

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

Vai continuar jogando golfe e postar uma explicação mais tarde. A abordagem básica é permitir que o mecanismo regex faça o trabalho duro com a correspondência de cadeias. Por exemplo, ele construirá uma regex semelhante ae ^(.{3})*(.{7})*(.{8})*$corresponderá a uma cadeia de comprimento em nque ndesce do produto das entradas até que ela não corresponda.

Observe que isso se tornará exponencialmente lento à medida que o número de argumentos aumentar.

Uso: Os argumentos são lidos em STDIN (nova linha separada), por exemplo:

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)))])

Experimente online!

$a_i$outercolSums

Uma versão mais rápida, porém mais longa (por dois bytes) considera apenas max(a):

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

Uma versão ligeiramente mais curto (78 bytes) que na maioria das vezes leva muito log ou muito espaço para correr em Experimente on-line é

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

O segundo recuo é renderizado como 4 espaços no SO, essas devem ser tabulações.

Na verdade, uma solução 'rápida', não a força bruta, usa o 'Método de Wilf', conforme descrito aqui .

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)

Versão 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)}

Teste:

"[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
})