tło

Oficjalną walutą wyimaginowanego narodu Golfenistanu jest foo , a w obiegu są tylko trzy rodzaje monet: 3 foos, 7 foos i 8 foos. Widać, że za te monety nie można płacić określonych kwot, takich jak 4 karty. Niemniej jednak można utworzyć wszystkie wystarczająco duże ilości. Twoim zadaniem jest znalezienie największej kwoty, której nie można utworzyć za pomocą monet (w tym przypadku 5 pianek), co jest znane jako problem z monetami .

Wejście

Twój wkład to lista liczb całkowitych dodatnich, reprezentujących wartości monet w obiegu. Gwarantujemy dwie rzeczy:L = [n1, n2, ..., nk]

• GCD elementów Lwynosi 1.
• L nie zawiera cyfry 1.

Może być nieposortowany i / lub zawierać duplikaty (pomyśl monety specjalne).

Wynik

Ponieważ GCD Lwynosi 1, każda wystarczająco duża liczba całkowita mmoże być wyrażona jako nieujemna liniowa kombinacja jej elementów; innymi słowy mamy

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

dla niektórych liczb całkowitych . Twój wynik jest największą liczbą całkowitą, której nie można wyrazić w tej formie. Jako podpowiedź wiadomo, że wynik jest zawsze mniejszy niż , jeśli i są maksymalnymi i minimalnymi elementami ( odniesienia ).ai ≥ 0(n1 - 1)*(nk - 1)n1nkL

Zasady

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Jeśli Twój język ma wbudowaną operację, nie możesz go używać. Nie ma wymagań dotyczących czasu ani wydajności pamięci, z wyjątkiem tego, że powinieneś być w stanie ocenić przypadki testowe przed opublikowaniem odpowiedzi.

Po opublikowaniu tego wyzwania użytkownik @vihan wskazał, że przepełnienie stosu ma dokładną kopię . Na podstawie tej dyskusji Meta to wyzwanie nie zostanie usunięte jako duplikat; jednak proszę, aby wszystkie odpowiedzi oparte na odpowiedziach na wersję SO cytowały oryginały, otrzymały status Wiki Wiki i zostały usunięte, jeśli oryginalny autor chce zamieścić tutaj swoją odpowiedź.

Przypadki testowe

[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 bajty

ef!fqTs.b*NYQY^UTlQS*FQ

Jest bardzo wolny, ponieważ sprawdza wszystkie wartości aż do iloczynu wszystkich monet. Oto wersja, która jest prawie identyczna, ale 1) zmniejsza zestaw monet do tych, które nie są ze sobą podzielne, i 2) sprawdza tylko wartości do (max(coins) - 1) * (min(coins) - 1)(47 bajtów):

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

Wyjaśnienie

                   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 bajtów

Kod 50 bajtów + wiersz poleceń 1 bajt

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

Będzie kontynuował grę w golfa i opublikuje wyjaśnienie później. Podstawowym podejściem jest umożliwienie silnikowi wyrażeń regularnych ciężkiej pracy z dopasowaniem ciągów. Na przykład skonstruuje wyrażenie regularne podobne do ^(.{3})*(.{7})*(.{8})*$i dopasowujące do ciągu długości, w nktórym nzstępuje od iloczynu danych wejściowych, dopóki nie dopasuje.

Zauważ, że stanie się to wykładniczo wolne wraz ze wzrostem liczby argumentów.

Sposób użycia: Argumenty są wczytywane ze STDIN (nowy wiersz oddzielony), na przykład:

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

R , 84 78 bajtów

W celu samowolnego wprowadzenia kopii, $a_1, a_2,\ldots$, Kwotę Frobeniusa podaje

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

Wypróbuj online!

ponieważ jest zawsze mniejszy niż produkt ekstremalny $a_i$„s. Jest to zatem kwestia połączenia wszystkich możliwych kombinacji (i więcej) w tym zakresie. Dzięki Cole Beck za sugestie outerbez „*” i colSumszamiast „zastosuj (..., 2, suma) '.

Wersja szybsza, ale dłuższa (o dwa bajty) uwzględnia tylko max(a):

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

Nieco krótsza wersja (78 bajtów), która najczęściej trwa zbyt zalogować lub zbyt dużo miejsca, aby uruchomić na Spróbuj go online jest

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

Python2, 188 187 bajtów

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

Drugie wcięcie jest renderowane jako 4 spacje na SO, powinny to być tabulatory.

W rzeczywistości „szybkie” rozwiązanie, nie brutalne, wykorzystuje „Wilf's Method”, jak opisano tutaj .

JavaScript ES6, 120 130 126 128 127 125 znaków

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)

Alternatywna wersja 126 znaków:

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

Test:

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