Hintergrund

Die offizielle Währung der imaginären Nation Golfenistan ist das Foo , und es sind nur drei Arten von Münzen im Umlauf: 3 Foos, 7 Foos und 8 Foos. Man kann sehen, dass es nicht möglich ist, mit diesen Münzen bestimmte Beträge wie 4 Foos zu bezahlen. Trotzdem können alle ausreichend großen Mengen gebildet werden. Ihre Aufgabe ist es, den größten Betrag zu finden, der mit den Münzen nicht gebildet werden kann (in diesem Fall 5 Foos), der als Münzenproblem bekannt ist .

Eingang

Ihre Eingabe ist eine Liste positiver Ganzzahlen, die die Werte der im Umlauf befindlichen Münzen darstellen. Zwei Dinge sind dabei garantiert:L = [n1, n2, ..., nk]

• Die GCD der Elemente von List 1.
• L enthält nicht die Nummer 1.

Es kann unsortiert sein und / oder Duplikate enthalten (denken Sie an Münzen in Sonderausgabe).

Ausgabe

Da der GCD von L1 ist, kann jede ausreichend große ganze Zahl mals eine nicht negative lineare Kombination ihrer Elemente ausgedrückt werden; Mit anderen Worten, wir haben

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

für einige ganze Zahlen . Ihre Ausgabe ist die größte Ganzzahl, die in dieser Form nicht ausgedrückt werden kann . Als Hinweis ist bekannt, dass die Ausgabe immer kleiner ist als , wenn und sind die maximalen und minimalen Elemente von ( Referenz ).ai ≥ 0(n1 - 1)*(nk - 1)n1nkL

Regeln

Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig. Wenn in Ihrer Sprache hierfür eine Funktion integriert ist, können Sie diese möglicherweise nicht verwenden. Es gibt keine Anforderungen an die Zeit- oder Speichereffizienz, außer dass Sie in der Lage sein sollten, die Testfälle zu bewerten, bevor Sie Ihre Antwort veröffentlichen.

Nachdem ich diese Challenge gepostet hatte, wies Benutzer @vihan darauf hin, dass Stack Overflow ein genaues Duplikat hat . Basierend auf dieser Metadiskussion wird diese Herausforderung nicht als Duplikat gelöscht. Ich bitte jedoch darum, dass in allen Antworten, die auf den Antworten der SO-Version basieren, die Originale zitiert, der Community-Wiki-Status zugewiesen und diese gelöscht werden, wenn der ursprüngliche Autor ihre Antwort hier veröffentlichen möchte.

Testfälle

[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 ist sehr langsam, da es alle Werte bis zum Produkt aller Münzen überprüft. Hier ist eine Version, die fast identisch ist, aber 1) die Menge der Münzen auf diejenigen reduziert, die nicht durch einander teilbar sind und 2) nur Werte bis zu (max(coins) - 1) * (min(coins) - 1)(47 Byte) prüft :

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

Erläuterung

                   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

50 Byte Code + 1 Byte Befehlszeile

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

Ich werde weiter Golf spielen und später eine Erklärung abgeben. Der grundlegende Ansatz besteht darin, die Regex-Engine die harte Arbeit mit dem String-Matching erledigen zu lassen. Beispielsweise wird ein regulärer Ausdruck erstellt, der ^(.{3})*(.{7})*(.{8})*$einer Zeichenfolge ähnelt und mit dieser übereinstimmt, nwobei er nvom Produkt der Eingaben abweicht, bis er nicht mehr übereinstimmt.

Beachten Sie, dass dies mit zunehmender Anzahl der Argumente exponentiell langsam wird.

Verwendung: Argumente werden aus STDIN eingelesen (durch neue Zeile getrennt), zum Beispiel:

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

Probieren Sie es online!

$a_i$outercolSums

Eine schnellere, aber längere (um zwei Bytes) Version berücksichtigt nur max(a):

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

Eine etwas kürzere Version (78 Byte), die meistens zu viel Protokoll oder Speicherplatz benötigt, um online ausgeführt zu werden, ist Try it online

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

Der zweite Einzug wird als 4 Leerzeichen auf SO gerendert, dies sollten Tabulatoren sein.

Eigentlich eine ‚schnelle‘ Lösung, nicht Brute - Force, Verwendungen ‚Wilfs Methode‘ , wie hier .

Javascript ES6, 120 130 126 128 127 125 Zeichen

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)

Alternative 126-Zeichen-Version:

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

Prüfung:

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