Un pastel de tres frutas está hecho de tres frutas diferentes . ¿Cuál es la mayor cantidad de pasteles de tres frutas que puedes hacer de las cantidades de 5 frutas que tienes?

Por ejemplo, con

1 apple
1 banana
4 mangoes 
2 nectarines
0 peaches

puedes hacer 2 pasteles:

apple, mango, nectarine
banana, mango, nectarine

Entrada: Cinco enteros no negativos, o una lista de ellos.

Salida: El número máximo de pasteles de tres frutas que puede hacer de esas cantidades de fruta. Pocos bytes ganan.

Casos de prueba:

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

Tabla de clasificación:

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 por @FryAmTheEggman

Programa de 14 bytes por @isaacg

Afirmo que el número de pasteles que se pueden formar a partir de una lista ascendente [x1,x2,x3,x4,x5]es:

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

O en código:

JSQhS/Ls~PJ_S3

[Vea el historial de revisiones para los programas TI-BASIC y APL]

Prueba de corrección

Dejar

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

Queremos demostrar que P(X)=floor(min(s5/3,s4/2,s3))siempre es el mayor número de pasteles para una lista x1≤x2≤x3≤x4≤x5de números de frutas 1 ~ 5.

Primero, mostramos que los tres números son límites superiores.

• Dado que hay s5frutas totales, y cada pastel tiene tres frutas, ⌊s5/3⌋es un límite superior.

• Dado que hay s4frutas que no son frutas 5, y se requieren al menos dos frutas que no son 5 en cada pastel, ⌊s4/2⌋es un límite superior.

• Como hay s3frutas que no son ni fruta 4 ni fruta 5, y se requiere al menos una de esas frutas en cada pastel, s3es un límite superior.

En segundo lugar, mostramos que el método de tomar frutos de las tres pilas más grandes siempre satisface el límite. Hacemos esto por inducción.

Caso base: obviamente, se pueden formar 0 pasteles a partir de cualquier lista válida con P(X)>=0.

Paso inductivo: dada cualquier lista Xdonde P(X) > 0, podemos hornear un pastel, dejando una lista X'con P(X') >= P(X)-1. Hacemos esto tomando una fruta de las tres pilas más grandes 3,4,5y luego recurriendo si es necesario. Tengan paciencia conmigo; Hay algunos casos.

• Si x2<x3, entonces no necesitamos ordenar la lista después de eliminar las frutas. Ya tenemos un válido X'. Sabemos que P(X') = P(X)-1porque s5'es 3 menos (porque se eliminaron tres frutas de tipo 1 ~ 5), s4'es 2 menos y s3'es 1 menos. Entonces P(X')es exactamente uno menos que P (X).
• Si x3<x4, entonces hemos terminado de manera similar.

• Ahora tomamos el caso donde x2=x3=x4. Tendremos que reorganizar la lista esta vez.

  • Si x5>x4, entonces reorganizamos la lista cambiando las pilas 4 y 2. s5'y s4'todavía hay una disminución de 3 y 2 respectivamente, pero s3'=s3-2. Esto no es un problema, porque si x2=x3=x4, entonces 2*x4<=s3-> 2*x4+s3 <= 2*s3-> (x4 + s4)/2 <= s3. Tenemos dos subcajas:

  • Igualdad, es decir (x4,x3,x2,x1)=(1,1,1,0), en cuyo caso P(X)= 1y claramente podemos hacer un pastel a partir de pilas 5,4,3, o:

  • (s4+1)/2 <= s3, en cuyo caso una disminución s4adicional 1no significa una disminución adicional a P (X).

• Ahora nos quedamos con el caso donde x1<x2=x3=x4=x5. Ahora s3también se reducirá en 1, por lo que debemos (s5/3+1)ser <=s4/2; es decir 8x5+2x1+2<=9x5+3x1, o x5+x1>=2. Todos los casos más pequeños que esto se pueden verificar manualmente.

• Si cada número es igual, está claro que podemos lograr el límite de ⌊s5/3⌋, que siempre es menor que los otros dos; simplemente pasamos por los números en secuencia.

Finalmente hemos terminado. Comente si me falta algo, y le daré una pequeña recompensa por una prueba más elegante.

CJam, 34

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

Pruébalo en línea

Explicación:

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]

Esto define una función fque toma en la lista de frutas xy devuelve el número máximo de pasteles.

Explicación

Calculamos el número de pasteles de forma recursiva. La parte se mapM(\a->a:[a-1|a>0])xevalúa en la lista de todas las listas obtenidas xal disminuir cualquier entrada positiva. Si x = [0,1,2], resulta en

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

La parte entre el exterior []es una comprensión de la lista: iteramos a través de todo yen la lista anterior y filtramos aquellos cuya suma no es igual sum(x)-3, por lo que obtenemos todas las listas donde se han hecho 3 frutas diferentes en un pastel. Luego evaluamos recursivamente fen estas listas, agregamos 1a cada una y tomamos el máximo de ellas y 0(el caso base, si no podemos hacer pasteles).

C #, 67

Recurrentemente haga un pastel por iteración con las frutas que tenga más hasta que se acabe.

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

Prueba casos aquí

Pyth, 29

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

Banco de pruebas

Ordena la lista de entrada y elimina los ceros. Luego, siempre que tenga 3 frutas, disminuya el primero y los dos últimos elementos, y agregue los elementos restantes a la lista, antes de ordenarlos y eliminar ceros nuevamente. Luego incremente un contador en 1.

En realidad, esto es bastante rápido siempre que solo haya 5 frutas, puede resolver contenedores de frutas muy grandes, es decir, 1000,1000,1000,1000,1000en menos de un segundo.

Python, solución general, 128 92 bytes

-36 bytes de @xnor, eres un verdadero 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)

Esto funciona siempre que mi prueba sea ​​correcta. Si no es así, avíseme por qué para intentar solucionarlo. Si es incomprensible, avíseme y lo atacaré después de unas tazas de café.

Python 2, 78 bytes

Tomando 5 números como entrada: 91 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 : Cambio s=sorted([input()for x in[0]*5])por s=sorted(map(input,['']*5));x=0guardar 1 byte.

Toma 5 números como entrada e imprime el número de pasteles posibles que se pueden hacer. Toma el mismo enfoque que la respuesta de Reto Koradi -sin mejorar el conteo de bytes- pero parecía que a esta pregunta le faltaba una respuesta en Python.

Gracias @ThomasKwa y @xsot por su sugerencia.

Cómo 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

Tenga en cuenta que la variable xnunca se define, pero el programa aprovecha algunas fugas que tiene Python 2.7. Al definir la lista scon la comprensión de la lista, el último valor en el iterable ( [0]*5en este caso) se almacena en la variable utilizada para iterar.

Para aclarar las cosas:

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

Tomando una lista como entrada: 78 bytes

Gracias @xnor @xsot y @ThomasKwa por sugerir cambiar la entrada a una lista.

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

Cómo funciona

Funciona de la misma manera que el código anterior, pero en este caso la entrada ya es una lista, por lo que no es necesario crearla y xse debe definir la variable .

Descargo de responsabilidad: este es mi primer intento de jugar al golf y parece que todavía se puede jugar al golf, así que sugiera cualquier cambio que pueda hacerse para reducir el conteo de bytes.

CJam, 23 bytes

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

Pruébalo en línea

Esto toma fruto de las 3 pilas más grandes en cada iteración, y cuenta el número de iteraciones.

No tengo una prueba matemática de que esto siempre dé el resultado correcto. Lo hace para los ejemplos de prueba dados, y creo que funciona para todos los casos hasta que alguien me dé un contraejemplo.

La explicación intuitiva que utilicé para convencerme a mí mismo: para maximizar el número de pasteles, debe mantener tantas pilas no vacías como sea posible. Esto se debe a que pierde la capacidad de hacer más pasteles tan pronto como tenga 3 o más pilas vacías.

Esto se logra tomando siempre fruta de las pilas más grandes. No puedo pensar en un caso en el que tomar fruta de una pila más pequeña conduzca a una situación mejor que tomar fruta de una pila más grande.

Tengo un razonamiento un poco más formal en mi cabeza. Trataré de pensar en una forma de ponerlo en palabras / fórmula.

> <>, 76 bytes

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

Resulta que ordenar en> <> no es fácil. Este programa se basa en la prueba presentada por Thomas Kwa para ser cierta, que ciertamente parece ser el caso con los casos de prueba.

Se espera que los 5 números de entrada estén presentes en la pila al inicio del programa.

Las primeras dos líneas clasifican los números en la pila, y la tercera realiza el cálculo floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3)), tomado de la respuesta de Thomas.

Python 2, 59 bytes

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

Un método general que funciona para cualquier ny k. Esto k=3hace que las frutas por pastel sean predeterminadas a 3, pero puede pasar un valor diferente. La recursión utiliza el hecho de que las cadenas son más grandes que los números en Python 2, dejando que la cadena vacía represente el caso base del infinito.

Este método utiliza el hecho de que tomar siempre la fruta más común es óptimo, por lo que consideramos cada posible rango de fruta como un factor limitante. He reprendido ese hecho a continuación.

La prueba de Mego me hizo pensar en esta prueba más directa de que tomar repetidamente las frutas más comunes es óptimo. Esto se afirma con pasteles de kfrutas.

Teorema: tomar repetidamente las kfrutas más comunes da la cantidad óptima de pasteles.

Prueba: demostraremos que si los Npasteles son posibles, entonces la estrategia de fruta más común produce al menos Npasteles. Hacemos esto cambiando las frutas entre los Npasteles para que coincidan con los producidos por esta estrategia, mientras mantenemos los pasteles válidos.

Hagamos que el primer pastel (llámelo p) contenga las frutas más comunes. Si aún no lo hace, debe contener una fruta i, pero no una fruta más común j. Entonces, los pasteles restantes tienen estrictamente más fruta jque fruta i, por lo que otros pasteles qdeben contener jpero no i. Luego, podemos intercambiar fruta ide pastel ppor fruta jde pastel q, lo que hace que los Npasteles tengan fruta distinta.

Repita este proceso hasta que ptenga las kfrutas más comunes.

Luego, ponga el pastel a pun lado y repita este proceso para el próximo pastel para que tenga las frutas restantes más comunes. Siga haciendo esto hasta que los pasteles sean la secuencia producida por la estrategia de fruta más común.

PowerShell, 92 bytes

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

Utiliza el mismo algoritmo basado en la codicia que la respuesta de FryAmTheEggman ... pero mucho más eficaz en 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}