Pie tiga buah terbuat dari tiga buah yang berbeda . Apa pai paling tiga buah yang bisa Anda buat dari jumlah 5 buah yang Anda miliki?

Misalnya dengan

1 apple
1 banana
4 mangoes 
2 nectarines
0 peaches

Anda dapat membuat 2 kue:

apple, mango, nectarine
banana, mango, nectarine

Input: Lima bilangan bulat non-negatif, atau daftar bilangan bulat.

Keluaran: Jumlah maksimum tiga pai buah yang dapat Anda buat dari jumlah buah tersebut. Bytes paling sedikit menang.

Kasus uji:

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

Papan peringkat:

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 byte

-1 byte oleh @FryAmTheEggman

Program 14 byte oleh @isaacg

Saya mengklaim bahwa jumlah pai yang dapat dibentuk dari daftar naik [x1,x2,x3,x4,x5]adalah:

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

Atau dalam kode:

JSQhS/Ls~PJ_S3

[Lihat riwayat revisi untuk program TI-BASIC dan APL]

Bukti kebenaran

Membiarkan

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

Kami ingin menunjukkan bahwa P(X)=floor(min(s5/3,s4/2,s3))selalu ada jumlah pai terbesar untuk daftar x1≤x2≤x3≤x4≤x5jumlah buah 1 ~ 5.

Pertama, kami menunjukkan bahwa ketiga angka adalah batas atas.

• Karena ada s5total buah, dan masing-masing pai memiliki tiga buah, ⌊s5/3⌋adalah batas atas.

• Karena ada s4buah - buahan yang bukan buah 5, dan setidaknya dua buah non-5 diperlukan di setiap pie, ⌊s4/2⌋adalah batas atas.

• Karena ada s3buah - buahan yang bukan buah 4 atau buah 5, dan setidaknya satu buah seperti itu diperlukan dalam setiap pie, s3adalah batas atas.

Kedua, kami menunjukkan bahwa metode mengambil buah dari tiga tumpukan terbesar selalu memenuhi batas. Kami melakukan ini dengan induksi.

Kasus dasar: 0 pai jelas dapat dibentuk dari daftar apa pun yang valid dengannya P(X)>=0.

Langkah induktif: Mengingat setiap daftar Xdi mana P(X) > 0, kita bisa membakar satu pie, meninggalkan daftar X'dengan P(X') >= P(X)-1. Kami melakukan ini dengan mengambil buah dari tiga tumpukan terbesar 3,4,5, lalu memilih jika diperlukan. Tetap bersamaku; ada beberapa kasus.

• Jika x2<x3, maka kita tidak perlu mengurutkan daftar setelah menghapus buah. Kami sudah memiliki yang valid X'. Kita tahu bahwa P(X') = P(X)-1karena s5'3 lebih sedikit (karena tiga buah tipe 1 ~ 5 telah dihapus), s4'2 lebih sedikit, dan s3'1 lebih sedikit. Jadi P(X')persis satu kurang dari P (X).
• Jika x3<x4, maka kita sudah selesai.

• Sekarang kita bawa kasing kemana x2=x3=x4. Kami perlu mengatur ulang daftar saat ini.

  • Jika x5>x4, maka kita mengatur ulang daftar dengan menukar tumpukan 4 dan 2. s5'dan s4'masih penurunan masing-masing 3 dan 2, tetapi s3'=s3-2. Ini bukan masalah, karena jika x2=x3=x4, maka 2*x4<=s3-> 2*x4+s3 <= 2*s3-> (x4 + s4)/2 <= s3. Kami memiliki dua sub-bagian:

  • Kesetaraan, yaitu (x4,x3,x2,x1)=(1,1,1,0), dalam hal ini P(X)= 1dan kita dapat dengan jelas membuat pai dari tumpukan 5,4,3, atau:

  • (s4+1)/2 <= s3, dalam hal mana penurunan s4dengan tambahan 1tidak berarti penurunan ekstra ke P (X).

• Sekarang kita pergi dengan kasing di mana x1<x2=x3=x4=x5. Sekarang s3juga akan menurun 1, jadi kita perlu (s5/3+1)untuk menjadi <=s4/2; itu adalah 8x5+2x1+2<=9x5+3x1,, atau x5+x1>=2. Semua kasing yang lebih kecil dari ini dapat diperiksa secara manual.

• Jika setiap bilangan sama, jelas bahwa kita dapat mencapai batas ⌊s5/3⌋, yang selalu lebih rendah dari dua bilangan lainnya — kita cukup menelusuri bilangan secara berurutan.

Akhirnya kita selesai. Tolong beri komentar jika saya kehilangan sesuatu, dan saya akan memberikan hadiah kecil untuk bukti yang lebih elegan.

CJam, 34

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

Cobalah online

Penjelasan:

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 byte

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

Ini mendefinisikan fungsi fyang mengambil dalam daftar buah xdan mengembalikan jumlah maksimum pai.

Penjelasan

Kami menghitung jumlah pai secara rekursif. Bagian mapM(\a->a:[a-1|a>0])xmengevaluasi daftar semua daftar yang diperoleh xdengan mengurangi setiap entri positif. Jika x = [0,1,2], itu menghasilkan

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

Bagian antara bagian luar []adalah pemahaman daftar: kita beralih melalui semua yyang ada di daftar di atas dan menyaring mereka yang jumlahnya tidak sama dengan sum(x)-3, jadi kita mendapatkan semua daftar di mana 3 buah yang berbeda telah dibuat menjadi pai. Kemudian kami secara rekursif mengevaluasi fdaftar-daftar ini, menambahnya 1masing-masing, dan mengambilnya secara maksimal dan 0(kasus dasar, jika kami tidak dapat membuat pai apa pun).

C #, 67

Secara rekursif buat satu pai per iterasi dengan buah-buahan yang paling Anda miliki sampai habis.

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

Uji kasus di sini

Pyth, 29

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

Suite uji

Mengurutkan daftar input dan menghapus nol. Lalu, selama Anda memiliki 3 buah, kurangi elemen pertama dan dua terakhir, dan tambahkan elemen yang tersisa ke daftar, sebelum mengurutkannya dan menghapus nol lagi. Kemudian menambah penghitung dengan 1.

Ini sebenarnya agak cepat asalkan hanya ada 5 buah, bisa dipecahkan untuk tempat sampah buah yang sangat besar, yaitu 1000,1000,1000,1000,1000di bawah satu detik.

Python, solusi umum, 128 92 byte

-36 byte dari @xnor, Anda da mvp nyata

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)

Ini berfungsi selama bukti saya benar. Jika tidak, beri tahu saya mengapa saya bisa memperbaikinya. Jika tidak bisa dimengerti, beri tahu saya, dan saya akan menyerangnya setelah beberapa cangkir kopi.

Python 2, 78 byte

Mengambil 5 angka sebagai input: 91 89 88 byte

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

Sunting : Mengganti s=sorted([input()for x in[0]*5])dengan s=sorted(map(input,['']*5));x=0menghemat 1 byte.

Mengambil 5 angka sebagai input dan mencetak jumlah pai yang mungkin dibuat. Dibutuhkan pendekatan yang sama dengan jawaban Reto Koradi - tanpa meningkatkan jumlah byte - tetapi rasanya seperti pertanyaan ini tidak ada jawaban dalam Python.

Terima kasih @ThomasKwa dan @xsot atas saran Anda.

Bagaimana itu bekerja

 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

Perhatikan bahwa variabel xtidak pernah didefinisikan, tetapi program mengambil keuntungan dari beberapa kebocoran python 2.7. Ketika mendefinisikan daftar sdengan pemahaman daftar nilai terakhir di iterable ( [0]*5dalam hal ini) disimpan dalam variabel yang digunakan untuk beralih.

Untuk memperjelas:

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

Mengambil daftar sebagai input: 78 byte

Terima kasih @xnor @xsot dan @ThomasKwa karena menyarankan mengubah input ke daftar.

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

Bagaimana itu bekerja

Ia bekerja dengan cara yang sama dengan kode di atas, tetapi dalam hal ini input sudah menjadi daftar sehingga tidak perlu membuatnya dan variabel xharus didefinisikan.

Penafian: Ini adalah upaya pertama saya untuk bermain golf dan rasanya masih bisa bermain golf, jadi sarankan setiap perubahan yang dapat dilakukan untuk mengurangi jumlah byte.

CJam, 23 byte

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

Cobalah online

Ini mengambil buah dari 3 tumpukan terbesar di setiap iterasi, dan menghitung jumlah iterasi.

Saya tidak punya bukti matematika bahwa ini selalu memberikan hasil yang benar. Itu berlaku untuk contoh uji yang diberikan, dan saya akan percaya bahwa itu bekerja untuk semua kasus sampai seseorang memberi saya contoh balasan.

Penjelasan intuitif yang saya gunakan untuk meyakinkan diri saya sendiri: Untuk memaksimalkan jumlah pai, Anda harus menyimpan tumpukan sebanyak-banyaknya agar tidak kosong. Itu karena Anda kehilangan kemampuan untuk membuat lebih banyak kue segera setelah Anda memiliki 3 atau lebih tumpukan kosong.

Ini dicapai dengan selalu mengambil buah dari tumpukan terbesar. Saya tidak dapat memikirkan kasus di mana mengambil buah dari tumpukan yang lebih kecil akan mengarah pada situasi yang lebih baik daripada mengambil buah dari tumpukan yang lebih besar.

Saya memiliki alasan yang sedikit lebih formal di kepala saya. Saya akan mencoba memikirkan cara untuk memasukkannya ke dalam kata-kata / formula.

> <>, 76 byte

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

Ternyata menyortir>> tidak mudah! Program ini bergantung pada bukti yang diajukan oleh Thomas Kwa untuk menjadi kenyataan, yang tentunya terlihat seperti halnya dengan kasus-kasus uji.

5 nomor input diharapkan ada pada tumpukan di awal program.

Dua baris pertama mengurutkan angka pada stack, dan yang ketiga melakukan perhitungan floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3)), diambil dari jawaban Thomas.

Python 2, 59 byte

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

Metode umum yang bekerja untuk semua ndan k. The k=3membuat buah per bawaan pie untuk 3, tetapi Anda dapat lulus dalam nilai yang berbeda. Rekursi menggunakan fakta bahwa string lebih besar daripada angka dalam Python 2, membiarkan string kosong mewakili kasus dasar infinity.

Metode ini menggunakan fakta bahwa selalu mengambil buah yang paling umum adalah optimal, jadi kami menganggap setiap peringkat buah sebagai faktor pembatas. Saya sudah mencela fakta di bawah ini.

Bukti Mego membuat saya memikirkan bukti yang lebih langsung ini bahwa berulang kali mengambil buah yang paling umum adalah optimal. Ini dinyatakan dengan pai kbuah.

Teorema: Mengambil kbuah yang paling umum secara berulang memberikan jumlah pai yang optimal.

Bukti: Kami akan menunjukkan bahwa jika Npai dimungkinkan, maka strategi yang paling umum menghasilkan setidaknya Npai. Kami melakukan ini dengan beralih buah di antara Npai untuk membuatnya cocok dengan yang dihasilkan oleh strategi ini, sambil menjaga pai tetap valid.

Mari kita membuatnya sehingga pie pertama (sebut saja p) mengandung buah yang paling umum. Jika belum, itu harus mengandung buah i, tetapi bukan buah yang lebih umum j. Kemudian, pai yang tersisa memiliki lebih banyak buah jdaripada buah i, dan beberapa pai lainnya qharus mengandung jtetapi tidak i. Kemudian, kita dapat bertukar buah idari pai pdengan buah jdari pai q, yang membuat Npai memiliki buah yang berbeda.

Ulangi proses ini hingga pmenghasilkan kbuah yang paling umum.

Kemudian, psisihkan pai , dan ulangi proses ini untuk pai berikutnya untuk membuatnya memiliki sisa buah yang paling umum. Terus lakukan ini sampai pai adalah urutan yang diproduksi oleh negara buah yang paling umum.

PowerShell, 92 Bytes

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

Menggunakan algoritma berbasis serakah yang sama dengan jawaban FryAmTheEggman ... hanya lebih banyak kata di 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}