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
L
wynosi 1. L
nie zawiera cyfry 1.
Może być nieposortowany i / lub zawierać duplikaty (pomyśl monety specjalne).
Wynik
Ponieważ GCD L
wynosi 1, każda wystarczająco duża liczba całkowita m
moż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)
n1
nk
L
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
źródło
FrobeniusNumber
w Mathematica.(p - 1)(q - 1)
jako górną granicę, gdziep
iq
są najmniejszym i największym elementem zestawu.[2,3]
w rozsądnym czasie i nic więcej.[2,5]
stworzy w pamięci około miliona list Pythona.Odpowiedzi:
Pyth, 23 bajty
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):Wyjaśnienie
źródło
Perl,
605451 bajtówKod 50 bajtów + wiersz poleceń 1 bajt
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, wn
którymn
zstę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:
źródło
R ,
8478 bajtówW celu samowolnego wprowadzenia kopii,za1, a2), … , Kwotę Frobeniusa podaje
Wypróbuj online!
ponieważ jest zawsze mniejszy niż produkt ekstremalnyzaja „s. Jest to zatem kwestia połączenia wszystkich możliwych kombinacji (i więcej) w tym zakresie. Dzięki Cole Beck za sugestie
outer
bez „*” icolSums
zamiast „zastosuj (..., 2, suma) '.Wersja szybsza, ale dłuższa (o dwa bajty) uwzględnia tylko
max(a)
: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
źródło
Python2,
188187 bajtówDrugie 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 .
źródło
JavaScript ES6,
120130126128127125 znakówAlternatywna wersja 126 znaków:
Test:
źródło
forEach(
zmap(