Trzy owocowe ciasto składa się z trzech różnych owoców. Jakie są najbardziej owocowe ciasta z trzech owoców, jakie możesz zrobić?

Na przykład za pomocą

1 apple
1 banana
4 mangoes 
2 nectarines
0 peaches

możesz zrobić 2 ciasta:

apple, mango, nectarine
banana, mango, nectarine

Dane wejściowe: pięć liczb całkowitych nieujemnych lub ich lista.

Wyjście: maksymalna liczba placków z trzema owocami, które można zrobić z tych ilości owoców. Wygrywa najmniej bajtów.

Przypadki testowe:

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

Tabela liderów:

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

-1 bajt @FryAmTheEggman

14-bajtowy program @isaacg

Twierdzę, że liczba ciast, które można uformować z rosnącej listy, [x1,x2,x3,x4,x5]wynosi:

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

Lub w kodzie:

JSQhS/Ls~PJ_S3

[Zobacz historię zmian dla programów TI-BASIC i APL]

Dowód poprawności

Pozwolić

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

Chcemy pokazać, że P(X)=floor(min(s5/3,s4/2,s3))jest to zawsze największa liczba ciast na liściex1≤x2≤x3≤x4≤x5 liczb owoców 1 ~ 5.

Po pierwsze, pokazujemy, że wszystkie trzy liczby są górnymi granicami.

• Ponieważ są s5wszystkie owoce, a każde ciasto ma trzy owoce, ⌊s5/3⌋jest górną granicą.

• Ponieważ istnieją s4owoce, które nie są owocami 5, a co najmniej dwa owoce inne niż 5 są wymagane w każdym cieście, ⌊s4/2⌋górna granica.

• Ponieważ istnieją s3owoce, które nie są ani owocami 4, ani owocami 5, a przynajmniej jeden taki owoc jest wymagany w każdym cieście, s3jest to górna granica.

Po drugie, pokazujemy, że metoda zbierania owoców z trzech największych stosów zawsze spełnia oczekiwania. Robimy to przez indukcję.

Przypadek podstawowy: 0 ciastek można oczywiście utworzyć z dowolnej prawidłowej listy z P(X)>=0.

Indukcyjny krok: Biorąc pod uwagę żadnej listy X, gdzie P(X) > 0możemy upiec jeden placek, zostawiając listy X'z P(X') >= P(X)-1. Robimy to, pobierając owoce z trzech największych stosów 3,4,5, a następnie uciekając w razie potrzeby. Zrób ze mną; jest trochę spraw.

• Jeśli x2<x3, to nie musimy sortować listy po usunięciu owoców. Mamy już ważnyX' . Wiemy, że P(X') = P(X)-1ponieważ s5'jest o 3 mniej (ponieważ usunięto trzy owoce typu 1 ~ 5), s4'jest o 2 mniej i s3'jest o 1 mniej. Czyli P(X')dokładnie o jeden mniej niż P (X).
• Jeśli x3<x4to zrobimy podobnie.

• Teraz bierzemy przypadek gdzie x2=x3=x4. Tym razem będziemy musieli zmienić kolejność listy.

  • Jeśli x5>x4, to przestawiamy listę, zmieniając stosy 4 i 2. s5'i s4'nadal spadamy odpowiednio o 3 i 2, ale s3'=s3-2. To nie jest problem, ponieważ jeślix2=x3=x4 , to 2*x4<=s3-> 2*x4+s3 <= 2*s3-> (x4 + s4)/2 <= s3. Mamy dwie podklasy:

  • Równość, tj. (x4,x3,x2,x1)=(1,1,1,0)W którym przypadku P(X)=1 i możemy wyraźnie zrobić ciasto ze stosów 5,4,3lub:

  • (s4+1)/2 <= s3, w którym to przypadku zmniejsza s4się o dodatkowy1 nie oznacza dodatkowego zmniejszenia do P (X).

• Teraz pozostaje nam przypadek, w którym x1<x2=x3=x4=x5. Teraz s3również zostanie zmniejszona o 1, więc musimy (s5/3+1)być <=s4/2; to jest,8x5+2x1+2<=9x5+3x1 , lub x5+x1>=2. Wszystkie przypadki mniejsze niż to można sprawdzić ręcznie.

• Jeśli każda liczba jest równa, jasne jest, że możemy osiągnąć granicę ⌊s5/3⌋ , która jest zawsze mniejsza niż pozostałe dwie - po prostu przeglądamy liczby w sekwencji.

Wreszcie skończyliśmy. Proszę o komentarz, jeśli coś mi umknie, a ja dam małą nagrodę za bardziej elegancki dowód.

CJam, 34

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

Wypróbuj online

Wyjaśnienie:

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 bajty

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

Definiuje funkcję, fktóra pobiera listę owoców xi zwraca maksymalną liczbę ciast.

Wyjaśnienie

Rekurencyjnie obliczamy liczbę ciast. Część mapM(\a->a:[a-1|a>0])xewaluuje do listy wszystkich list uzyskanych xprzez zmniejszenie wartości pozytywnych wpisów. Jeśli x = [0,1,2]spowoduje to

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

Część między zewnętrznym []jest rozumieniem listy: iterujemy wszystko yna powyższej liście i odfiltrowujemy tych, których suma nie jest równa sum(x)-3, więc otrzymujemy wszystkie listy, w których 3 różne owoce zostały przetworzone w ciasto. Następnie rekurencyjnie oceniamy fte listy, dodajemy 1do każdej z nich i bierzemy ich maksimum oraz 0(podstawowy przypadek, jeśli nie możemy zrobić żadnych ciast).

C #, 67

Rekurencyjnie zrób jedno ciasto na iterację z owocami, które masz najwięcej, aż do wyczerpania.

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

Przypadki testowe tutaj

Pyth, 29 lat

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

Zestaw testowy

Sortuje listę danych wejściowych i usuwa zera. Następnie, o ile masz 3 owoce, zmniejsz pierwszy i dwa ostatnie elementy i dodaj pozostałe elementy do listy, zanim posortujesz je i ponownie usuniesz zera. Następnie zwiększ licznik o 1.

Jest to faktycznie dość szybkie, o ile jest tylko 5 owoców, może rozwiązać bardzo duże pojemniki z owocami, tj. 1000,1000,1000,1000,1000W ciągu sekundy.

Python, rozwiązanie ogólne, 128 92 bajty

-36 bajtów od @xnor, da real 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)

Działa to tak długo, jak długo mój dowód jest poprawny. Jeśli nie, daj mi znać, dlaczego mogę spróbować to naprawić. Jeśli jest to niezrozumiałe, daj mi znać, a zaatakuję go po kilku filiżankach kawy.

Python 2, 78 bajtów

Biorąc 5 liczb jako dane wejściowe: 91 89 88 bajtów

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

Edycja : Zmiana s=sorted([input()for x in[0]*5])o s=sorted(map(input,['']*5));x=0zapisuje 1 bajt.

Pobiera 5 liczb jako dane wejściowe i drukuje liczbę możliwych ciasta, które można zrobić. Przyjmuje to samo podejście, co odpowiedź Reto Koradi - bez poprawiania liczby bajtów - ale wydawało się, że w pytaniu brakowało odpowiedzi.

Dzięki @ThomasKwa i @xsot za sugestię.

Jak to działa

 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

Zauważ, że zmienna xnigdy nie jest zdefiniowana, ale program korzysta z niektórych wycieków Pythona 2.7. Podczas definiowania listy sze zrozumieniem listy ostatnia wartość w iterowalnym ( [0]*5w tym przypadku) jest przechowywana w zmiennej używanej do iteracji.

Aby wszystko było jaśniejsze:

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

Biorąc listę jako dane wejściowe: 78 bajtów

Dzięki @xnor @xsot i @ThomasKwa za sugestię zmiany danych wejściowych na listę.

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

Jak to działa

Działa tak samo jak powyższy kod, ale w tym przypadku dane wejściowe są już listą, więc nie ma potrzeby ich tworzenia i xnależy zdefiniować zmienną .

Oświadczenie: To moja pierwsza próba gry w golfa i wydaje mi się, że nadal można grać w golfa, więc sugeruj wszelkie zmiany, które można wprowadzić, aby zmniejszyć liczbę bajtów.

CJam, 23 bajty

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

Wypróbuj online

Daje to owoce z 3 największych stosów w każdej iteracji i liczy liczbę iteracji.

Nie mam matematycznego dowodu, że zawsze daje to właściwy wynik. Działa w przypadku podanych przykładów testowych i uwierzę, że działa we wszystkich przypadkach, dopóki ktoś nie poda mi kontrprzykładu.

Intuicyjne wyjaśnienie, które sam sobie przekonywałem: Aby zmaksymalizować liczbę ciast, musisz zachować jak najwięcej stosów, które nie są puste. Dzieje się tak, ponieważ tracisz możliwość robienia większej liczby ciast, gdy tylko masz 3 lub więcej pustych stosów.

Osiąga się to zawsze biorąc owoce z największych stosów. Nie mogę wymyślić przypadku, w którym pobranie owoców z mniejszego stosu doprowadziłoby do lepszej sytuacji niż pobranie owoców z większego stosu.

Mam nieco bardziej formalne rozumowanie. Spróbuję wymyślić sposób, aby umieścić to w słowach / formule.

> <>, 76 bajtów

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

Okazuje się, że sortowanie w> <> nie jest łatwe! Program ten opiera się na prawdziwości dowodu przedstawionego przez Thomasa Kwa, co z pewnością wygląda na przypadek przypadków testowych.

Oczekuje się, że 5 liczb wejściowych będzie obecnych na stosie na początku programu.

Pierwsze dwa wiersze sortują liczby na stosie, a trzeci wykonuje obliczenia na podstawie floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3))odpowiedzi Thomasa.

Python 2, 59 bajtów

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

Ogólna metoda, która działa dla każdego n i k. k=3Sprawia, że owoce domyślnie pie do 3, ale można przejść na inną wartość. Rekurencja wykorzystuje fakt, że ciągi są większe niż liczby w Pythonie 2, pozwalając, aby pusty ciąg reprezentował podstawowy przypadek nieskończoności.

Ta metoda wykorzystuje fakt, że zawsze przyjmowanie najbardziej powszechnych owoców jest optymalne, dlatego uważamy każdą możliwą rangę owoców za czynnik ograniczający. Potwierdziłem ten fakt poniżej.

Dowód Mego sprawił, że pomyślałem o tym bardziej bezpośrednim dowodzie, że wielokrotne przyjmowanie najczęstszych owoców jest optymalne. Jest to stwierdzone w przypadku ciast kowocowych.

Twierdzenie: Wielokrotne przyjmowanie knajczęstszych owoców daje optymalną liczbę ciast.

Dowód: pokażemy, że jeśli Nciasta są możliwe, to strategia najczęstszych owoców produkuje przynajmniej Nciasta. Robimy to, zmieniając owoce w Ncieście, aby dopasować je do tych wyprodukowanych przez tę strategię, jednocześnie zachowując ważność ciast.

Zróbmy to, aby pierwsze ciasto (nazwij je p) zawierało najczęstsze owoce. Jeśli jeszcze nie ma, musi zawierać owoc i, ale nie bardziej powszechny owoc j. Następnie pozostałe ciasta mają więcej owoców jniż owoców i, więc niektóre inne ciasta qmuszą zawierać, jale nie muszą i. Następnie możemy zamienić owoce iz ciasta na powoce jz ciasta q, dzięki czemu Nciasta mają wyraźne owoce.

Powtórz ten proces, dopóki pma knajczęstsze owoce.

Następnie podłóż ciasto na bok i powtórz ten proces dla następnego ciasta, aby uzyskać najczęściej występujące owoce. Rób to dalej, aż ciasta będą sekwencją produkowaną przez strategię najczęstszych owoców.

PowerShell, 92 bajty

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

Używa tego samego algorytmu opartego na chciwości, co odpowiedź FryAmTheEggman ... o wiele bardziej tekstowa w 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}