Une tarte aux trois fruits est composée de trois fruits différents . Quelle est la plupart des tartes aux trois fruits que vous pouvez faire à partir des 5 fruits que vous avez?

Par exemple, avec

1 apple
1 banana
4 mangoes 
2 nectarines
0 peaches

vous pouvez faire 2 tartes:

apple, mango, nectarine
banana, mango, nectarine

Entrée: cinq entiers non négatifs ou une liste d'entre eux.

Sortie: Le nombre maximum de tartes aux trois fruits que vous pouvez faire à partir de ces quantités de fruits. Le moins d'octets gagne.

Cas de test:

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

Classement:

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 octets

-1 octet par @FryAmTheEggman

Programme de 14 octets par @isaacg

Je prétends que le nombre de tartes qui peuvent être formées à partir d'une liste ascendante [x1,x2,x3,x4,x5]est:

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

Ou en code:

JSQhS/Ls~PJ_S3

[Voir l'historique des révisions pour les programmes TI-BASIC et APL]

Preuve d'exactitude

Laisser

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

Nous voulons montrer que P(X)=floor(min(s5/3,s4/2,s3))c'est toujours le plus grand nombre de tartes pour une liste x1≤x2≤x3≤x4≤x5de nombres de fruits 1 ~ 5.

Premièrement, nous montrons que les trois nombres sont des bornes supérieures.

• Puisqu'il y a un s5total de fruits, et chaque tarte a trois fruits, ⌊s5/3⌋c'est une limite supérieure.

• Puisqu'il y a des s4fruits qui ne sont pas des fruits 5 et qu'au moins deux fruits non 5 sont nécessaires dans chaque tarte, ⌊s4/2⌋c'est une limite supérieure.

• Puisqu'il y a des s3fruits qui ne sont ni des fruits 4 ni des fruits 5, et au moins un tel fruit est requis dans chaque tarte, s3est une limite supérieure.

Deuxièmement, nous montrons que la méthode de prélèvement des fruits des trois plus gros tas satisfait toujours la limite. Nous le faisons par induction.

Cas de base: 0 tartes peuvent évidemment être formées à partir de n'importe quelle liste valide avec P(X)>=0.

Étape inductive: Étant donné n'importe quelle liste Xoù P(X) > 0, nous pouvons faire cuire une tarte, laissant derrière une liste X'avecP(X') >= P(X)-1 . Nous faisons cela en prenant un fruit des trois plus gros tas 3,4,5, puis en recourant si nécessaire. Restez avec moi; il y a du travail.

• Si x2<x3, alors nous n'avons pas besoin de trier la liste après avoir retiré les fruits. Nous avons déjà un valide X'. Nous savons que P(X') = P(X)-1parce que s5'c'est 3 de moins (parce que trois fruits de type 1 ~ 5 ont été retirés), s4'c'est 2 de moins, ets3' 1 de moins. P(X')Est donc exactement un de moins que P (X).
• Si x3<x4 , alors nous avons fait de même.

• Maintenant, nous prenons le cas où x2=x3=x4 . Nous devons réorganiser la liste cette fois.

  • Si x5>x4, alors nous réorganisons la liste en changeant les piles 4 et 2. s5'et s4'sommes toujours une diminution de 3 et 2 respectivement, mais s3'=s3-2. Ce n'est pas un problème, car si x2=x3=x4, alors 2*x4<=s3-> 2*x4+s3 <= 2*s3->(x4 + s4)/2 <= s3 . Nous avons deux sous-cas:

  • L'égalité, c'est (x4,x3,x2,x1)=(1,1,1,0)-à- dire , dans ce cas P(X)= 1et nous pouvons clairement faire une tarte à partir de tas 5,4,3, ou:

  • (s4+1)/2 <= s3, auquel cas une diminution s4supplémentaire 1ne signifie pas une diminution supplémentaire de P (X).

• Maintenant, nous nous retrouvons avec le cas où x1<x2=x3=x4=x5. Maintenant, s3sera également diminué de 1, nous devons (s5/3+1)donc être <=s4/2; c'est-à-dire 8x5+2x1+2<=9x5+3x1, ou x5+x1>=2. Tous les cas plus petits que cela peuvent être vérifiés manuellement.

• Si chaque nombre est égal, il est clair que nous pouvons atteindre la limite de ⌊s5/3⌋, qui est toujours inférieure aux deux autres - nous passons simplement par les nombres en séquence.

Enfin, nous avons terminé. Veuillez commenter si je manque quelque chose, et je donnerai une petite prime pour une preuve plus élégante.

CJam, 34

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

Essayez-le en ligne

Explication:

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 octets

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

Cela définit une fonction fqui prend la liste des fruits xet renvoie le nombre maximum de tartes.

Explication

Nous calculons le nombre de tartes de manière récursive. La partie est mapM(\a->a:[a-1|a>0])xévaluée à la liste de toutes les listes obtenues à partir xde la décrémentation des entrées positives. Si x = [0,1,2]cela se traduit par

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

La partie entre l'extérieur []est une compréhension de liste: nous parcourons tout ydans la liste ci-dessus et filtrons ceux dont la somme n'est pas égale sum(x)-3, nous obtenons donc toutes les listes où 3 fruits différents ont été transformés en tarte. Ensuite, nous évaluons récursivement fsur ces listes, ajoutons 1à chacune et prenons le maximum d'entre elles et 0(le cas de base, si nous ne pouvons pas faire de tartes).

C #, 67

Faites récursivement une tarte par itération avec les fruits que vous avez le plus jusqu'à épuisement.

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

Cas de test ici

Pyth, 29

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

Suite de tests

Trie la liste d'entrée et supprime les zéros. Ensuite, tant que vous avez 3 fruits, décrémentez le premier et les deux derniers éléments, et ajoutez les éléments restants à la liste, avant de la trier et de supprimer à nouveau les zéros. Incrémentez ensuite un compteur de 1.

C'est en fait assez rapide tant qu'il n'y a que 5 fruits, cela peut résoudre pour de très grandes corbeilles de fruits, c'est- 1000,1000,1000,1000,1000à- dire en moins d'une seconde.

Python, solution générale, 128 92 octets

-36 octets de @xnor, vous da mvp réel

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)

Cela fonctionne tant que ma preuve est correcte. Si ce n'est pas le cas, faites-moi savoir pourquoi afin que je puisse essayer de le réparer. Si c'est incompréhensible, faites-le moi savoir et je l'attaquerai après quelques tasses de café.

Python 2, 78 octets

Prendre 5 nombres en entrée: 91 89 88 octets

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

Modifier : la modification s=sorted([input()for x in[0]*5])par s=sorted(map(input,['']*5));x=0enregistre 1 octet.

Prend 5 chiffres en entrée et imprime le nombre de tartes possibles qui peuvent être faites. Il adopte la même approche que la réponse de Reto Koradi - sans améliorer le nombre d'octets - mais il semblait que cette question manquait de réponse en Python.

Merci @ThomasKwa et @xsot pour votre suggestion.

Comment ça marche

 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

Notez que la variable xn'est jamais définie, mais le programme profite d'une fuite de python 2.7. Lors de la définition de la liste savec compréhension de la liste, la dernière valeur de l'itérable ( [0]*5dans ce cas) est stockée dans la variable utilisée pour l'itération.

Pour rendre les choses plus claires:

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

Prendre une liste en entrée: 78 octets

Merci @xnor @xsot et @ThomasKwa d'avoir suggéré de changer l'entrée en liste.

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

Comment ça marche

Il fonctionne de la même manière que le code ci-dessus, mais dans ce cas, l'entrée est déjà une liste, il n'est donc pas nécessaire de la créer et une variable xdoit être définie.

Avis de non-responsabilité: il s'agit de ma première tentative de golf et il me semble qu'il peut toujours être joué, alors suggérez toutes les modifications qui pourraient être apportées afin de réduire le nombre d'octets.

CJam, 23 octets

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

Essayez-le en ligne

Cela prend des fruits des 3 plus gros tas de chaque itération et compte le nombre d'itérations.

Je n'ai pas de preuve mathématique que cela donne toujours le bon résultat. C'est le cas pour les exemples de test donnés, et je pense que cela fonctionne pour tous les cas jusqu'à ce que quelqu'un me donne un contre-exemple.

L'explication intuitive que j'ai utilisée pour me convaincre: Pour maximiser le nombre de tartes, vous devez garder autant de piles non vides que possible. C'est parce que vous perdez la possibilité de faire plus de tartes dès que vous avez 3 piles ou plus vides.

Ceci est réalisé en prenant toujours des fruits des plus gros tas. Je ne peux pas penser à un cas où prendre des fruits d'un plus petit tas conduirait à une meilleure situation que de prendre des fruits d'un plus gros tas.

J'ai un raisonnement un peu plus formel dans ma tête. Je vais essayer de trouver un moyen de le mettre en mots / formule.

> <>, 76 octets

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

Il s'avère que le tri dans> <> n'est pas facile! Ce programme s'appuie sur la preuve avancée par Thomas Kwa pour être vraie, ce qui semble certainement être le cas avec les cas de test.

Les 5 numéros d'entrée devraient être présents sur la pile au début du programme.

Les deux premières lignes trient les nombres sur la pile et la troisième effectue le calcul floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3)) , tiré de la réponse de Thomas.

Python 2, 59 octets

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

Une méthode générale qui fonctionne pour tout n et k. Le k=3rend les fruits par tarte par défaut à 3, mais vous pouvez passer une valeur différente. La récursivité utilise le fait que les chaînes sont plus grandes que les nombres en Python 2, laissant la chaîne vide représenter le cas de base de l'infini.

Cette méthode utilise le fait que toujours prendre le fruit le plus commun est optimal, donc nous considérons chaque rang de fruit possible comme un facteur limitant. J'ai repris ce fait ci-dessous.

La preuve de Mego m'a fait penser à cette preuve plus directe que la prise répétée des fruits les plus courants est optimale. Ceci est indiqué avec des tartes dek fruits.

Théorème: Prendre à plusieurs reprises lek des fruits plus courants donne le nombre optimal de tartes.

Preuve: Nous montrerons que si les Ntartes sont possibles, la stratégie de fruits la plus courante produit au moins des Ntartes. Nous le faisons en changeant les fruits entre lesN tartes pour les faire correspondre à ceux produits par cette stratégie, tout en gardant les tartes valides.

Faisons en sorte que la première tarte (appelez-la p) contienne les fruits les plus courants. Si ce n'est pas encore fait, il doit contenir un fruit i, mais pas un fruit plus commun j. Ensuite, les tartes restantes ont strictement plus de fruits jque de fruits i, et donc une autre tarte qdoit contenir jmais pas i. Ensuite, nous pouvons échanger des fruits ide tarte pavec des fruits jde tarteq , ce qui permet aux Ntartes d'avoir des fruits distincts.

Répétez ce processus jusqu'à ce que plek fruits soient plus courants.

Ensuite, mettez la tarte de pcôté et répétez ce processus pour la prochaine tarte pour lui donner les fruits restants les plus courants. Continuez ainsi jusqu'à ce que les tartes soient la séquence produite par la stratégie de fruits la plus courante.

PowerShell, 92 octets

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

Utilise le même algorithme gourmand que la réponse de FryAmTheEggman ... juste beaucoup plus verbeux dans 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}