Uma torta de três frutas é feita de três frutas diferentes . Qual é a maioria das tortas de três frutas que você pode fazer com a quantidade de 5 frutas que você tem?

Por exemplo, com

1 apple
1 banana
4 mangoes 
2 nectarines
0 peaches

você pode fazer 2 tortas:

apple, mango, nectarine
banana, mango, nectarine

Entrada: cinco números inteiros não negativos ou uma lista deles.

Saída: o número máximo de tortas de três frutas que você pode fazer com essas quantidades de frutas. Menos bytes ganha.

Casos de teste:

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

Entre os melhores:

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>

Pitão, 19 18 14 bytes

-1 byte por @FryAmTheEggman

Programa de 14 bytes por @isaacg

Afirmo que o número de tortas que podem ser formadas a partir de uma lista crescente [x1,x2,x3,x4,x5]é:

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

Ou no código:

JSQhS/Ls~PJ_S3

[Veja o histórico de revisões dos programas TI-BASIC e APL]

Prova de correção

Deixei

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

Queremos mostrar que P(X)=floor(min(s5/3,s4/2,s3))é sempre o maior número de tortas para uma lista x1≤x2≤x3≤x4≤x5de números de frutas 1 ~ 5.

Primeiro, mostramos que todos os três números são limites superiores.

• Como há s5frutas totais, e cada torta tem três frutas, ⌊s5/3⌋é um limite superior.

• Como existem s4frutas que não são frutas 5 e pelo menos duas frutas não-5 são necessárias em cada torta, ⌊s4/2⌋é um limite superior.

• Como existem s3frutas que não são frutas 4 nem frutas 5, e pelo menos uma dessas frutas é necessária em cada torta, s3é um limite superior.

Segundo, mostramos que o método de colher frutas das três maiores pilhas sempre satisfaz o limite. Fazemos isso por indução.

Caso base: obviamente, 0 tortas podem ser formadas a partir de qualquer lista válida P(X)>=0.

Etapa indutiva: Dada qualquer lista Xem P(X) > 0que possamos assar uma torta, deixando para trás uma lista X'com P(X') >= P(X)-1. Fazemos isso pegando uma fruta das três maiores pilhas 3,4,5e recorrendo, se necessário. Tenha paciência comigo; há algum caso.

• Se x2<x3, não precisamos classificar a lista após remover as frutas. Nós já temos um válido X'. Sabemos isso P(X') = P(X)-1porque s5'é 3 a menos (porque três frutas do tipo 1 a 5 foram removidas), s4'é 2 a menos e s3'é 1 a menos. Então, P(X')é exatamente um a menos que P (X).
• Se x3<x4, então somos feitos da mesma forma.

• Agora vamos levar o caso para onde x2=x3=x4. Precisamos reorganizar a lista dessa vez.

  • Se x5>x4, então, reorganizamos a lista alternando as pilhas 4 e 2. s5'e s4'ainda temos uma diminuição de 3 e 2 respectivamente, mas s3'=s3-2. Isso não é um problema, porque se x2=x3=x4, então 2*x4<=s3-> 2*x4+s3 <= 2*s3-> (x4 + s4)/2 <= s3. Temos duas subcasas:

  • Igualdade, ou seja (x4,x3,x2,x1)=(1,1,1,0), nesse caso P(X)= 1e podemos fazer claramente uma torta de pilhas 5,4,3, ou:

  • (s4+1)/2 <= s3, nesse caso, diminuir s4um extra 1não significa um decréscimo extra para P (X).

• Agora ficamos com o caso em que x1<x2=x3=x4=x5. Agora s3também será reduzido em 1, então precisamos (s5/3+1)ser <=s4/2; isto é 8x5+2x1+2<=9x5+3x1, ou x5+x1>=2. Todos os casos menores que isso podem ser verificados manualmente.

• Se todo número é igual, fica claro que podemos alcançar o limite de ⌊s5/3⌋, que é sempre menor que os outros dois - simplesmente passamos pelos números em sequência.

Finalmente terminamos. Comente se estiver faltando alguma coisa, e darei uma pequena recompensa por uma prova mais elegante.

CJam, 34

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

Experimente online

Explicação:

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]

Isso define uma função fque recebe a lista de frutas xe retorna o número máximo de tortas.

Explicação

Computamos o número de tortas recursivamente. A peça é mapM(\a->a:[a-1|a>0])xavaliada para a lista de todas as listas obtidas x, diminuindo as entradas positivas. Se x = [0,1,2]isso resultar em

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

A parte entre o exterior []é uma compreensão da lista: iteramos por todos yna lista acima e filtramos aqueles cuja soma não é igual a sum(x)-3, então obtemos todas as listas em que três frutas diferentes foram transformadas em uma torta. Em seguida, avaliamos recursivamente fessas listas, adicionamos 1a cada uma e obtemos o máximo delas e 0(o caso base, se não podemos fazer tortas).

C #, 67

Recursivamente, faça uma torta por iteração com as frutas que você tem mais até acabar.

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

Casos de teste aqui

Pyth, 29

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

Suíte de teste

Classifica a lista de entrada e remove os zeros. Então, contanto que você tenha 3 frutas, diminua o primeiro e os dois últimos elementos e adicione os elementos restantes à lista, antes de classificá-la e remover os zeros novamente. Aumente um contador em 1.

Isso é realmente rápido, desde que existam apenas cinco frutas, ele pode resolver grandes caixas de frutas, ou seja, 1000,1000,1000,1000,1000em menos de um segundo.

Python, solução geral, 128 92 bytes

-36 bytes de @xnor, você é mvp real

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)

Isso funciona desde que minha prova esteja correta. Caso contrário, informe-me o motivo para tentar consertá-lo. Se for incompreensível, avise-me e atacarei depois de algumas xícaras de café.

Python 2, 78 bytes

Tomando 5 números como entrada: 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

Editar : Alterar s=sorted([input()for x in[0]*5])por s=sorted(map(input,['']*5));x=0salva 1 byte.

Pega 5 números como entrada e imprime o número de tortas possíveis que podem ser feitas. Ele segue a mesma abordagem da resposta de Reto Koradi, sem melhorar a contagem de bytes, mas parecia que essa pergunta estava faltando uma resposta no Python.

Obrigado @ThomasKwa e @xsot pela sua sugestão.

Como funciona

 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

Observe que a variável xnunca é definida, mas o programa tira proveito de algumas fugas que o python 2.7 possui. Ao definir a lista scom compreensão da lista, o último valor no iterável ( [0]*5neste caso) é armazenado na variável usada para iterar.

Para tornar as coisas mais claras:

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

Tomando uma lista como entrada: 78 bytes

Obrigado @xnor @xsot e @ThomasKwa por sugerirem alterar a entrada para uma lista.

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

Como funciona

Funciona da mesma maneira que o código acima, mas neste caso a entrada já é uma lista, portanto não há necessidade de criá-lo e a variável xdeve ser definida.

Isenção de responsabilidade: Esta é minha primeira tentativa de jogar golfe e parece que ainda pode ser jogado, por isso sugira quaisquer alterações que possam ser feitas para reduzir a contagem de bytes.

CJam, 23 bytes

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

Experimente online

Isso extrai frutos das 3 maiores pilhas de cada iteração e conta o número de iterações.

Não tenho uma prova matemática de que isso sempre dê o resultado correto. Isso funciona para os exemplos de teste fornecidos, e acreditarei que funcione para todos os casos até que alguém me dê um contra-exemplo.

A explicação intuitiva que usei para me convencer: para maximizar o número de tortas, você precisa manter o maior número possível de pilhas não vazias. Isso ocorre porque você perde a capacidade de fazer mais tortas assim que tiver 3 ou mais pilhas vazias.

Isso é conseguido sempre com frutas das maiores pilhas. Não consigo pensar em um caso em que pegar frutas de uma pilha menor levaria a uma situação melhor do que pegar frutas de uma pilha maior.

Eu tenho um raciocínio um pouco mais formal na minha cabeça. Vou tentar pensar em uma maneira de colocá-lo em palavras / fórmula.

> <>, 76 bytes

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

Acontece que classificar> <> não é fácil! Este programa baseia-se na prova apresentada por Thomas Kwa para ser verdadeira, o que certamente parece ser o caso dos casos de teste.

Espera-se que os 5 números de entrada estejam presentes na pilha no início do programa.

As duas primeiras linhas classificam os números na pilha e a terceira realiza o cálculo floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3)), retirado da resposta de Thomas.

Python 2, 59 bytes

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

Um método geral que funciona para qualquer ne k. O k=3padrão torna os frutos por torta em 3, mas você pode transmitir um valor diferente. A recursão usa o fato de que as strings são maiores que os números no Python 2, permitindo que a string vazia represente o caso base do infinito.

Esse método usa o fato de que sempre é ótimo consumir a fruta mais comum, por isso consideramos cada categoria possível de frutas como um fator limitante. Eu reprovei esse fato abaixo.

A prova de Mego me fez pensar nessa prova mais direta de que pegar repetidamente os frutos mais comuns é o ideal. Isto é afirmado com tortas de kfrutas.

Teorema: Tomar repetidamente as kfrutas mais comuns fornece o número ideal de tortas.

Prova: mostraremos que, se as Ntortas forem possíveis, a estratégia de frutas mais comuns produz pelo menos Ntortas. Fazemos isso trocando frutas entre as Ntortas para torná-las iguais às produzidas por essa estratégia, mantendo as tortas válidas.

Vamos fazer com que a primeira torta (chame p) contenha as frutas mais comuns. Se ainda não o fez, deve conter uma fruta i, mas não uma fruta mais comum j. Então, as tortas restantes têm estritamente mais frutas do jque frutas ie, portanto, outra torta qdeve conter, jmas não i. Em seguida, podemos trocar frutas ida torta ppor frutas jda torta q, o que mantém as Ntortas com frutas distintas.

Repita esse processo até obter pos kfrutos mais comuns.

Em seguida, preserve a torta e repita esse processo para a próxima, para que ela tenha os frutos restantes mais comuns. Continue fazendo isso até que as tortas sejam a sequência produzida pela estratégia de frutas mais comuns.

PowerShell, 92 bytes

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

Usa o mesmo algoritmo guloso que a resposta de FryAmTheEggman ... muito mais elaborada no 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}