Пирог из трех фруктов состоит из трех разных фруктов. Какие пироги из трех фруктов вы можете приготовить из 5 фруктов?

Например, с

1 apple
1 banana
4 mangoes 
2 nectarines
0 peaches

Вы можете сделать 2 пирога:

apple, mango, nectarine
banana, mango, nectarine

Входные данные: пять неотрицательных целых чисел или список из них.

Выход: максимальное количество пирогов с тремя фруктами, которые вы можете сделать из этого количества фруктов. Побеждает несколько байтов.

Тестовые случаи:

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

Leaderboard:

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 байтов

-1 байт @FryAmTheEggman

14-байтовая программа @isaacg

Я утверждаю, что число пирогов, которые могут быть сформированы из возрастающего списка [x1,x2,x3,x4,x5]:

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

Или в коде:

JSQhS/Ls~PJ_S3

[Смотрите историю изменений для программ TI-BASIC и APL]

Доказательство правильности

Позволять

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

Мы хотим показать, что P(X)=floor(min(s5/3,s4/2,s3))всегда самое большое количество пирогов для списка x1≤x2≤x3≤x4≤x5номеров фруктов 1 ~ 5.

Сначала покажем, что все три числа являются верхними границами.

• Так как есть s5всего фруктов, и у каждого пирога есть три фрукты, ⌊s5/3⌋это верхняя граница.

• Поскольку есть s4фрукты, которые не являются фруктами 5, и, по крайней мере, два не 5 фруктов требуются в каждом пироге, ⌊s4/2⌋это верхняя граница.

• Поскольку есть s3фрукты, которые не являются ни фруктами 4, ни фруктами 5, и по крайней мере один такой фрукт требуется в каждом пироге, s3это верхняя граница.

Во-вторых, мы показываем, что метод взятия плодов из трех самых больших куч всегда удовлетворяет пределу. Мы делаем это по индукции.

Базовый случай: 0 пирогов могут быть сформированы из любого допустимого списка с помощью P(X)>=0.

Индуктивный шаг: учитывая любой список, Xгде P(X) > 0мы можем испечь один пирог, оставив список X'с P(X') >= P(X)-1. Мы делаем это, беря фрукты из трех самых больших груд 3,4,5, а затем прибегая к помощи, если это необходимо. Потерпите меня; есть некоторые дела.

• Если x2<x3, тогда нам не нужно сортировать список после удаления фруктов. У нас уже есть действительный X'. Мы знаем, что P(X') = P(X)-1потому что s5'на 3 меньше (потому что три плода типа 1 ~ 5 были удалены), s4'на 2 меньше, а s3'на 1 меньше. Так P(X')что ровно на единицу меньше, чем P (X).
• Если x3<x4, то мы так же сделали.

• Теперь возьмем случай, когда x2=x3=x4. Нам нужно изменить список на этот раз.

  • Если x5>x4, то мы переставляем список, переключая стопки 4 и 2. s5'и s4'все еще уменьшаемся на 3 и 2 соответственно, но s3'=s3-2. Это не проблема, потому что если x2=x3=x4, тогда 2*x4<=s3-> 2*x4+s3 <= 2*s3-> (x4 + s4)/2 <= s3. У нас есть два варианта:

  • Равенство, т. Е. (x4,x3,x2,x1)=(1,1,1,0)В каком случае P(X)= 1и мы можем четко сделать пирог из груд 5,4,3, или:

  • (s4+1)/2 <= s3в этом случае уменьшение s4на дополнительное 1не означает дополнительного уменьшения до P (X).

• Теперь мы остались с делом, где x1<x2=x3=x4=x5. Теперь s3также будет уменьшен на 1, поэтому мы должны (s5/3+1)быть <=s4/2; то есть 8x5+2x1+2<=9x5+3x1или x5+x1>=2. Все случаи меньше этого можно проверить вручную.

• Если все числа равны, то ясно, что мы можем достичь границы ⌊s5/3⌋, которая всегда меньше двух других - мы просто перебираем числа в последовательности.

Наконец мы закончили. Пожалуйста, прокомментируйте, если я что-то упустил, и я дам маленькую награду за более элегантное доказательство.

CJam, 34

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

Попробуйте онлайн

Объяснение:

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 байта

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

Это определяет функцию, fкоторая берет список фруктов xи возвращает максимальное количество пирогов.

объяснение

Мы вычисляем количество пирогов рекурсивно. Эта часть mapM(\a->a:[a-1|a>0])xоценивается как список всех списков, полученных xпутем уменьшения числа положительных записей. Если x = [0,1,2]это приводит к

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

Часть между внешним []является списочным пониманием: мы перебираем все yв приведенном выше списке и отфильтровываем те, чья сумма не равна sum(x)-3, поэтому мы получаем все списки, в которых 3 разных фрукта были превращены в пирог. Затем мы рекурсивно оцениваем fэти списки, добавляем 1в каждый из них и берем максимум из них и 0(базовый случай, если мы не можем сделать какие-либо пироги).

C #, 67

Рекурсивно сделайте один пирог за итерацию с фруктами, которых у вас больше всего, пока не закончится.

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

Тестовые случаи здесь

Пиф, 29

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

Тестирование

Сортирует список ввода и удаляет нули. Затем, если у вас есть 3 фрукта, уменьшите первый и два последних элемента и добавьте остальные элементы в список, прежде чем сортировать его и снова удалять нули. Затем увеличьте счетчик на 1.

Это на самом деле довольно быстро, поскольку есть только 5 фруктов, это может решить для очень больших бункеров фруктов, то есть 1000,1000,1000,1000,1000менее чем за секунду.

Python, общее решение, 128 92 байта

-36 байт от @xnor, ты настоящий 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)

Это работает, пока мои доказательства верны. Если это не так, дайте мне знать, почему я могу попытаться это исправить. Если это непонятно, дайте мне знать, и я нападу на него после нескольких чашек кофе.

Python 2, 78 байт

Принимая 5 чисел в качестве ввода 91 89 88 байт

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

Изменить : изменение s=sorted([input()for x in[0]*5])на s=sorted(map(input,['']*5));x=01 байт.

Принимает 5 чисел в качестве входных данных и печатает количество возможных пирогов, которые можно сделать. В нем используется тот же подход, что и в ответе Рето Коради - без улучшения количества байтов - но казалось, что в этом вопросе отсутствует ответ в Python.

Спасибо @ThomasKwa и @xsot за ваше предложение.

Как это работает

 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

Обратите внимание, что переменная xникогда не определяется, но программа принимает некоторые утечки в Python 2.7. При определении списка sс пониманием списка последнее значение в итерируемом ( [0]*5в данном случае) сохраняется в переменной, используемой для итерации.

Чтобы прояснить ситуацию:

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

Принимая список в качестве входных данных: 78 байт

Спасибо @xnor @xsot и @ThomasKwa за предложение изменить вход в список.

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

Как это работает

Он работает так же, как и в приведенном выше коде, но в этом случае входные данные уже являются списком, поэтому нет необходимости его создавать, и xнеобходимо определить переменную .

Отказ от ответственности: это моя первая попытка игры в гольф, и я чувствую, что в нее все еще можно играть, поэтому предложите любые изменения, которые можно внести, чтобы уменьшить количество байтов.

CJam, 23 байта

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

Попробуйте онлайн

Это извлекает плоды из 3 самых больших куч в каждой итерации и подсчитывает количество итераций.

У меня нет математического доказательства того, что это всегда дает правильный результат. Это относится к приведенным тестовым примерам, и я верю, что это работает для всех случаев, пока кто-нибудь не даст мне контрпример.

Интуитивное объяснение, которое я использовал, чтобы убедить себя: чтобы максимизировать количество пирогов, вам нужно сохранить как можно больше пустых стопок. Это потому, что вы теряете возможность делать больше пирогов, как только у вас есть 3 или более пустых стопок.

Это достигается тем, что всегда берут фрукты из самых больших куч. Я не могу вспомнить случай, когда взятие фруктов из небольшой кучи привело бы к лучшей ситуации, чем получение фруктов из большой кучи.

У меня в голове немного более формальные рассуждения. Я постараюсь придумать способ выразить это словами / формулами.

> <>, 76 байт

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

Оказывается, сортировка в> <> не легка! Эта программа опирается на доказательство, выдвинутое Томасом Ква, чтобы быть правдой, что, безусловно, имеет место в тестовых случаях.

Ожидается, что 5 входных чисел будут присутствовать в стеке при запуске программы.

Первые две строки сортируют числа в стеке, а третья выполняет вычисления floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3)), взятые из ответа Томаса.

Python 2, 59 байт

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

Общий метод, который работает для любого nи k. По k=3умолчанию для фруктов на пирог установлено значение 3, но вы можете передать другое значение. В рекурсии используется тот факт, что в Python 2 строки больше, чем числа, что позволяет пустой строке представлять базовый случай бесконечности.

Этот метод использует тот факт, что всегда брать наиболее распространенные фрукты является оптимальным, поэтому мы рассматриваем каждый возможный сорт фруктов в качестве ограничивающего фактора. Я упрекнул этот факт ниже.

Доказательство Мего заставило меня подумать об этом более прямом доказательстве того, что повторное употребление наиболее распространенных фруктов является оптимальным. Об этом говорится в пирогах с kфруктами.

Теорема: Повторное употребление kсамых распространенных фруктов дает оптимальное количество пирогов.

Доказательство: мы покажем, что если Nпироги возможны, то стратегия с наиболее распространенными фруктами дает как минимум Nпироги. Мы делаем это, переключая фрукты между Nпирогами, чтобы они соответствовали фруктам , произведенным этой стратегией, сохраняя при этом пироги действительными.

Давайте сделаем так, чтобы первый пирог (назовите его p) содержал самые распространенные фрукты. Если это еще не так, он должен содержать фрукты i, но не более распространенный фрукт j. Тогда оставшиеся пироги содержат больше фруктов, jчем фруктов i, и поэтому некоторые другие пироги qдолжны содержать, jно не содержать i. Тогда мы можем поменять фруктыi с пирога pна фрукты jс пирога q, который сохраняет Nпироги с разными фруктами.

Повторяйте этот процесс, пока pне получите kсамые распространенные плоды.

Затем pотложите пирог и повторите этот процесс для следующего пирога, чтобы у него были самые распространенные оставшиеся фрукты. Продолжайте делать это до тех пор, пока пироги не станут последовательностью, созданной самой распространенной формой фруктов.

PowerShell, 92 байта

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

Использует тот же алгоритм, основанный на жадности, что и ответ FryAmTheEggman ... просто намного сложнее в 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}