Ein Drei-Früchte-Kuchen besteht aus drei verschiedenen Früchten. Was sind die meisten Drei-Früchte-Torten, die Sie aus den Mengen von 5 Früchten herstellen können?

Zum Beispiel mit

1 apple
1 banana
4 mangoes 
2 nectarines
0 peaches

Sie können 2 Kuchen machen:

apple, mango, nectarine
banana, mango, nectarine

Eingabe: Fünf nicht negative ganze Zahlen oder eine Liste davon.

Ausgabe: Die maximale Anzahl von drei Obstkuchen, die Sie aus diesen Obstmengen herstellen können. Wenigste Bytes gewinnt.

Testfälle:

1 1 4 2 0
2
2 2 2 2 2
3
0 6 0 6 0
0
12 5 3 2 1
5
1 14 14 3 2
6
0 0 1 0 50
0

Bestenliste:

var QUESTION_ID=59192,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Pyth, 19 18 14 Bytes

-1 Byte von @FryAmTheEggman

14-Byte-Programm von @isaacg

Ich behaupte, dass die Anzahl der Kuchen, die aus einer aufsteigenden Liste gebildet werden können, [x1,x2,x3,x4,x5]ist:

floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3))

Oder im Code:

JSQhS/Ls~PJ_S3

[Siehe Versionsverlauf für TI-BASIC- und APL-Programme]

Beweis der Richtigkeit

Lassen

s3 = x1+x2+x3
s4 = x1+x2+x3+x4
s5 = x1+x2+x3+x4+x5

Wir wollen zeigen, dass P(X)=floor(min(s5/3,s4/2,s3))immer die größte Anzahl von Torten für eine Liste x1≤x2≤x3≤x4≤x5von Anzahl von Früchten 1 ~ 5 ist.

Zunächst zeigen wir, dass alle drei Zahlen obere Schranken sind.

• Da es s5insgesamt Früchte gibt und jeder Kuchen drei Früchte hat, ⌊s5/3⌋ist eine Obergrenze.

• Da es s4Früchte gibt, die nicht Frucht 5 sind, und in jeder Torte mindestens zwei Nicht-5-Früchte erforderlich sind, ⌊s4/2⌋ist eine Obergrenze.

• Da es s3Früchte gibt, die weder Frucht 4 noch Frucht 5 sind und in jeder Torte mindestens eine solche Frucht erforderlich s3ist , ist eine Obergrenze.

Zweitens zeigen wir, dass die Methode, Früchte von den drei größten Haufen zu nehmen, immer die Grenze erfüllt. Wir machen das durch Induktion.

Basisfall: Aus jeder gültigen Liste mit können natürlich 0 Torten gebildet werden P(X)>=0.

Induktionsschritt: jede Liste gegeben , Xwo P(X) > 0können wir einen Kuchen backen, hinter einer Liste zu verlassen X'mit P(X') >= P(X)-1. Wir tun dies, indem wir eine Frucht von den drei größten Haufen nehmen 3,4,5und bei Bedarf erneut greifen . Trage mit mir; Es gibt ein paar Fälle.

• Wenn x2<x3ja, müssen wir die Liste nach dem Entfernen der Früchte nicht sortieren. Wir haben bereits eine gültige X'. Wir wissen , dass P(X') = P(X)-1da s5'drei weniger ist (weil drei Früchte vom Typ 1 bis 5 entfernt wurden), s4'2 weniger ist, und s3'ist 1 weniger. Ist P(X')also genau eins weniger als P (X).
• Wenn ja x3<x4, dann sind wir ähnlich fertig.

• Nun nehmen wir den Fall wo x2=x3=x4. Diesmal müssen wir die Liste neu ordnen.

  • Wenn x5>x4, dann ordnen wir die Liste von Pfählen 4 und 2. Schalten s5'und s4'sind immer noch ein Rückgang von 3 bzw. 2, aber s3'=s3-2. Das ist kein Problem, denn wenn x2=x3=x4, dann 2*x4<=s3-> 2*x4+s3 <= 2*s3-> (x4 + s4)/2 <= s3. Wir haben zwei Unterfälle:

  • Gleichheit, dh (x4,x3,x2,x1)=(1,1,1,0)in welchem ​​Fall P(X)= 1und wir können eindeutig einen Kuchen aus Haufen machen 5,4,3, oder:

  • (s4+1)/2 <= s3In diesem Fall bedeutet das Verringern s4um ein Extra 1kein zusätzliches Verringern auf P (X).

• Jetzt bleiben wir bei dem Fall, wo x1<x2=x3=x4=x5. Jetzt s3wird auch um 1 verringert, also müssen wir (s5/3+1)sein <=s4/2; das heißt 8x5+2x1+2<=9x5+3x1, oder x5+x1>=2. Alle kleineren Fälle können manuell überprüft werden.

• Wenn jede Zahl gleich ist, ist es klar, dass wir die Grenze von erreichen können ⌊s5/3⌋, die immer kleiner ist als die beiden anderen - wir gehen die Zahlen einfach der Reihe nach durch.

Endlich sind wir fertig. Bitte kommentieren Sie, wenn mir etwas fehlt, und ich werde ein kleines Kopfgeld für einen eleganteren Beweis geben.

CJam, 34

q~L{J2be!\f{\.-_W#){j)7}|;}0+:e>}j

Probieren Sie es online aus

Erläuterung:

q~          read and evaluate the input array
L{…}j       calculate with memoized recursion and no initial values
             using the input array as the argument
  J2b       convert 19 to base 2 (J=19), obtaining [1 0 0 1 1]
  e!        get permutations without duplicates
             these are all the combinations of three 1's and two 0's
             which represent the choices of fruit for one pie
  \         swap with the argument array
  f{…}      for each combination and the argument
    \       swap to bring the combination to the top
    .-      subtract from the argument array, item by item
    _       duplicate the resulting array
    W#)     does it contain the value -1? (calculate (index of W=-1) + 1)
    {…}|    if not
      j     recursively solve the problem for this array
      )7    increment the result, then push a dummy value
    ;       pop the last value (array containing -1 or dummy value)
  0+        add a 0 in case the resulting array is empty
             (if we couldn't make any pie from the argument)
  :e>       get the maximum value (best number of pies)

Haskell, 62 Bytes

f x=maximum$0:[1+f y|y<-mapM(\a->a:[a-1|a>0])x,sum y==sum x-3]

Dies definiert eine Funktion f, die die Fruchtliste aufnimmt xund die maximale Anzahl von Torten zurückgibt.

Erläuterung

Wir berechnen die Anzahl der Torten rekursiv. Der Teil mapM(\a->a:[a-1|a>0])xwertet alle Listen aus, die xdurch Dekrementieren aller positiven Einträge erhalten wurden. Wenn x = [0,1,2], ergibt sich

[[0,1,2],[0,1,1],[0,0,2],[0,0,1]]

Der Teil zwischen dem Äußeren []ist ein Listenverständnis: Wir durchlaufen alle yoben genannten Listen und filtern diejenigen heraus, deren Summe nicht gleich ist sum(x)-3, sodass wir alle Listen erhalten, in denen 3 verschiedene Früchte zu einer Torte verarbeitet wurden. Dann werten wir fdiese Listen rekursiv aus , addieren 1sie und nehmen das Maximum von ihnen und 0(der Grundfall, wenn wir keine Torten machen können).

C #, 67

Bilden Sie rekursiv eine Torte pro Iteration mit Früchten, die Sie am meisten haben, bis Sie ausgehen.

int f(List<int>p){p.Sort();p[3]--;p[4]--;return p[2]-->0?1+f(p):0;}

Testfälle hier

Pyth, 29

Wtt=QS-Q0=Q+tPPQtM>3.<Q1=hZ;Z

Testsuite

Sortiert die Eingabeliste und entfernt Nullen. Verringern Sie dann, solange Sie 3 Früchte haben, das erste und die beiden letzten Elemente und fügen Sie die verbleibenden Elemente zur Liste hinzu, bevor Sie sie sortieren und die Nullen wieder entfernen. Dann inkrementiere einen Zähler um 1.

Dies ist eigentlich ziemlich schnell, solange es nur 5 Früchte gibt, es kann für sehr große Fruchtbehälter, dh 1000,1000,1000,1000,1000in weniger als einer Sekunde, aufgelöst werden.

Python, allgemeine Lösung, 128 92 Bytes

-36 Bytes von @xnor, du bist ein richtiger MVP

g=lambda l,k:0if k>sum(l)else-(-1in l)or-~g(map(sum,zip(sorted(l),[0]*(len(l)-k)+[-1]*k)),k))

def g(a,k):b=[i for i in a if i];return 0if len(b)<k;c=sorted(b,reverse=True);return 1+g([c[i]-(k-1>i)for i in range(len(c))],k)

Dies funktioniert solange mein Beweis korrekt ist. Wenn dies nicht der Fall ist, lassen Sie mich wissen, warum, damit ich versuchen kann, das Problem zu beheben. Wenn es unverständlich ist, lassen Sie es mich wissen, und ich werde es nach ein paar Tassen Kaffee angreifen.

Python 2, 78 Bytes

Eingabe von 5 Zahlen: 91 89 88 Bytes

s=sorted([input()for x in[0]*5])
while s[2]:s[2]-=1;s[3]-=1;s[4]-=1;s.sort();x+=1
print x

Bearbeiten : Durch Ändern s=sorted([input()for x in[0]*5])von wird s=sorted(map(input,['']*5));x=01 Byte gespeichert.

Nimmt 5 Zahlen als Eingabe und druckt die Anzahl der möglichen Kuchen, die gemacht werden können. Es folgt dem gleichen Ansatz wie die Antwort von Reto Koradi - ohne die Anzahl der Bytes zu verbessern -, aber es schien, als würde diese Frage in Python nicht beantwortet.

Vielen Dank an @ThomasKwa und @xsot für Ihren Vorschlag.

Wie es funktioniert

 s=sorted([input()for x in[0]*5]) takes 5 numbers as input, puts them in a list 
                                  and sorts it in ascending order. The result
                                  is then stored in s 

 while s[2]:                      While there are more than 3 types of fruit 
                                  we can still make pies. As the list is                     
                                  sorted this will not be true when s[2] is 0. 
                                  This takes advantage of 0 being equivalent to False.

 s[2]-=1;s[3]-=1;s[4]-=1          Decrement in one unit the types of fruit 
                                  that we have the most

 s.sort()                         Sort the resulting list

 x+=1                             Add one to the pie counter

 print x                          Print the result

Beachten Sie, dass die Variable xniemals definiert wird, das Programm jedoch die Vorteile von Python 2.7 nutzt. Bei der Definition der Liste smit Listenverständnis wird der letzte Wert in der Iterationsdatei ( [0]*5in diesem Fall) in der zum Iterieren verwendeten Variablen gespeichert.

Um die Dinge klarer zu machen:

>>>[x for x in range(10)]
>>>x
9

Eingabe einer Liste: 78 Bytes

Vielen Dank an @xnor @xsot und @ThomasKwa für den Vorschlag, die Eingabe in eine Liste zu ändern.

s=sorted(input());x=0
while s[2]:s[2]-=1;s[3]-=1;s[4]-=1;s.sort();x+=1
print x

Wie es funktioniert

Es funktioniert genauso wie der obige Code, aber in diesem Fall ist die Eingabe bereits eine Liste, sodass es nicht erforderlich ist, sie zu erstellen, und eine Variable xmuss definiert werden.

Haftungsausschluss: Dies ist mein erster Versuch, Golf zu spielen, und ich habe das Gefühl, er kann noch gespielt werden. Schlagen Sie daher Änderungen vor, die vorgenommen werden könnten, um die Anzahl der Bytes zu verringern.

CJam, 23 Bytes

0l~{\)\$2/~+:(+_2=)}g;(

Probieren Sie es online aus

Dies entnimmt den drei größten Haufen in jeder Iteration Früchte und zählt die Anzahl der Iterationen.

Ich habe keinen mathematischen Beweis dafür, dass dies immer das richtige Ergebnis liefert. Dies gilt für die angegebenen Testbeispiele, und ich glaube, dass dies in allen Fällen funktioniert, bis mir jemand ein Gegenbeispiel gibt.

Die intuitive Erklärung, die ich verwendet habe, um mich selbst zu überzeugen: Um die Anzahl der Kuchen zu maximieren, müssen Sie so viele Stapel wie möglich nicht leer halten. Das liegt daran, dass Sie die Fähigkeit verlieren, mehr Kuchen zu machen, sobald Sie 3 oder mehr leere Stapel haben.

Dies wird erreicht, indem die Früchte immer von den größten Haufen genommen werden. Ich kann mir keinen Fall vorstellen, in dem die Entnahme von Obst von einem kleineren Stapel zu einer besseren Situation führen würde als die Entnahme von Obst von einem größeren Stapel.

Ich habe etwas formelleres Denken im Kopf. Ich werde versuchen, einen Weg zu finden, um es in Worte / Formeln zu fassen.

> <> 76 Bytes

0&4\/~}&?!/
@:@<\!?:}$-1@@$!?&+&:)@:@
,:&:@(?$n;/++:&+::2%-2,:&:@(?$&~+:3%-3

Es stellte sich heraus, dass das Sortieren in> <> nicht einfach ist! Dieses Programm stützt sich auf den von Thomas Kwa vorgebrachten Beweis für die Richtigkeit, was bei den Testfällen sicherlich der Fall zu sein scheint.

Es wird erwartet, dass die 5 Eingabenummern beim Programmstart auf dem Stapel vorhanden sind.

Die ersten beiden Zeilen sortieren die Zahlen auf dem Stapel, und die dritte Zeile berechnet floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3))sie anhand der Antwort von Thomas.

Python 2, 59 Bytes

h=lambda l,k=3:k*'_'and min(h(sorted(l)[:-1],k-1),sum(l)/k)

Eine allgemeine Methode, die für alle nund funktioniert k. Das k=3macht die Früchte pro Torte Standard bis 3, aber Sie in einem anderen Wert passieren können. Die Rekursion verwendet die Tatsache, dass Zeichenfolgen in Python 2 größer als Zahlen sind, sodass die leere Zeichenfolge den Grundfall der Unendlichkeit darstellt.

Diese Methode nutzt die Tatsache, dass es immer optimal ist, die am häufigsten vorkommenden Früchte zu nehmen. Daher betrachten wir jeden möglichen Rang der Früchte als begrenzenden Faktor. Ich habe diese Tatsache weiter unten widerlegt.

Megos Beweis ließ mich an diesen direkteren Beweis denken, dass die wiederholte Einnahme der häufigsten Früchte optimal ist. Dies wird mit Obstkuchen angegeben k.

Satz: Wiederholtes Nehmen der khäufigsten Früchte ergibt die optimale Anzahl von Torten.

Beweis: Wir werden zeigen, dass wenn NKuchen möglich sind, die gängigste Fruchtstrategie mindestens NKuchen hervorbringt . Wir tun dies, indem wir die Früchte zwischen den NTorten vertauschen, um sie mit denen dieser Strategie in Einklang zu bringen und gleichzeitig die Gültigkeit der Torten zu erhalten.

Lassen Sie es uns so machen, dass der erste Kuchen (nennen wir es p) die häufigsten Früchte enthält. Wenn dies noch nicht der Fall ist, muss es eine Frucht enthalten i, aber keine häufigere Frucht j. Dann haben die restlichen Torten streng mehr Obst jals Obst i, und so muss eine andere Torte qenthalten, jaber nicht i. Dann können wir Obst ivom Kuchen pgegen Obst tauschenj vom Kuchenq , wodurch NKuchen mit unterschiedlichen Früchten erhalten bleiben.

Wiederholen Sie diesen Vorgang bis p die khäufigsten Früchte haben.

Legen Sie dann die Torte pbeiseite und wiederholen Sie diesen Vorgang für die nächste Torte, damit sie die häufigsten verbleibenden Früchte enthält. Machen Sie so lange weiter, bis die Torten die Sequenz sind, die mit der gängigsten Fruchtstrategie erstellt wurde.

PowerShell, 92 Bytes

$a=($args|sort)-ne0;while($a.count-ge3){$a[0]--;$a[-1]--;$a[-2]--;$a=($a-ne0;$c++}($c,0)[!$c]

Verwendet denselben gierigen Algorithmus wie die Antwort von FryAmTheEggman ... nur viel wortreicher in PowerShell ....

$a=($args|sort)-ne0  # Take input arguments, sort them, remove any 0's
while($a.count-ge3){ # So long as we have 3 or more fruit piles
  $a[0]--            # Remove one from the first element...
  $a[-1]--           # ... the last element ...
  $a[-2]--           # ... and the second-to-last.
  $a=$a-ne0          # Remove any 0's from our piles
  $c++               # Increment how many pies we've made
}                    #
($c,0)[!$c]          # Equivalent to if($c){$c}else{0}