Saya memposting tantangan ini beberapa waktu lalu, yang menyangkut berapa banyak elf yang dibutuhkan Santa untuk mengirimkan hadiah.

Karena peningkatan populasi, Santa sedikit lebih terdesak untuk waktu tahun ini. Meskipun di masa lalu kami beroperasi sangat tidak serempak, kami mulai bereksperimen dengan semakin tersinkronisasi. Jadi, Santa perlu tahu berapa lama dia akan mengantarkan hadiah ke masing-masing daerah dengan sejumlah peri.

Berat batu bara tidak berubah selama dua tahun terakhir - masih lebih berat daripada hadiah, jadi Santa membutuhkan tiga elf per orang nakal di rumah, dan dua elf per orang baik di rumah.

Peri menghabiskan pelatihan sepanjang tahun untuk Natal, sehingga mereka tidak perlu istirahat di antara pengiriman. Mereka hanya dapat memberikan hadiah ke satu rumah pada satu waktu, dan harus kembali giring Santa dan mengumpulkan hadiah berikutnya sebelum pergi ke rumah berikutnya. Untuk alasan bahwa saya tidak bebas untuk berbagi, elf tidak menghabiskan waktu bepergian antara giring Santa dan rumah-rumah (tetapi hanya dapat melakukan perjalanan ketika giring Santa di atap), giringnya juga tidak menghabiskan waktu bergerak dari rumah ke rumah. (Giring Santa memang perlu bergerak dari rumah ke rumah untuk mengumpulkan bahan bakar, tapi aku sudah mengatakan terlalu banyak).

Elf yang mengirimkan hadiah harus menghabiskan empat detik ^* setiap pengiriman hadiah, dan Elf yang mengirimkan batubara perlu menghabiskan lima detik ^* masing-masing mengirimkannya (sesuai peraturan Santa Aviation Administration, sarung tangan dengan debu batu bara pada mereka harus dibakar segera setelah naik giring, yang memakan waktu). Selain itu, rumah-rumah harus dikunjungi dalam urutan di peta, dari kiri ke kanan, dan elf tidak dapat mulai mengirimkan hadiah ke rumah lain sampai semua hadiah dikirim ke rumah tempat mereka berada.

Jika kita mengasumsikan bahwa Santa memiliki elf lebih dari cukup untuk wilayah ini, hanya perlu selama yang diperlukan untuk mengirimkan hadiah kepada seseorang yang ada di daftar nakal, 5 detik, per rumah, atau 4 detik per rumah jika semua orang baik.

Namun, berbeda dengan musim-musim sebelumnya, Santa Natal yang akan datang ini mungkin tidak memiliki lebih dari cukup peri untuk setiap wilayah, jadi 4 detik adalah jumlah waktu minimum absolut ^* yang diperlukan untuk mengirimkan hadiah ke rumah mana pun, kecuali ada 0 orang baik dan 0 orang nakal dalam hal ini akan memakan waktu 0 detik.

Selain itu, jika bahkan salah satu rumah memiliki seseorang di daftar nakal, Santa akan membutuhkan setidaknya tiga elf. Jika setidaknya salah satu rumah memiliki seseorang dalam daftar yang bagus dan tidak satupun dari mereka memiliki orang-orang di daftar nakal, Santa akan membutuhkan setidaknya dua elf. Jika tidak ada rumah dalam semangat Natal, sejumlah elf (termasuk 0) akan membutuhkan 0 detik.

Pada peta Santa, sebuah rumah diwakili oleh a *, dan setiap rumah dibagi dengan a +. Santa masih menggunakan peta yang sama dengan tantangan lainnya , tetapi saya akan menyertakan dokumentasi tentang mereka di sini.

Akan ada angka di kedua sisi rumah - yang di sebelah kiri mewakili jumlah orang nakal di rumah, dan yang di sebelah kanan mewakili jumlah orang baik di rumah. Jika tidak ada angka di satu sisi itu ditafsirkan sebagai 0.

Saya tahu itu mungkin terdengar gila, tetapi beberapa orang "tidak suka Natal", jadi kadang-kadang, sebuah rumah mungkin tidak memiliki nomor di kedua sisinya.

Salah satu peta Santa bisa terlihat seperti ini.

1*3+2*+*5+*+4*7

Katakanlah Santa memiliki sembilan peri di giringnya.

1. (0d) Rumah pertama memiliki 1 orang nakal dan 3 orang baik. Tiga dari elf mengirimkan batubara, mengambil lima detik, dan enam memberikan hadiah, mengambil empat detik. Setelah lima detik, giring Santa bergerak ke rumah berikutnya

2. (5s) Rumah kedua memiliki 2 orang nakal dan 0 orang baik. Enam dari elf mengirimkan batubara, membutuhkan waktu lima detik. Setelah lima detik, giring Santa bergerak ke rumah berikutnya

3. (10-an) Rumah ketiga memiliki 0 nakal dan 5 orang baik. Delapan elf pergi untuk mengirimkan empat hadiah (yang tertinggal tidak dapat mengirimkan hadiah). Setelah empat detik, semua elf kembali, dan dua dari mereka pergi untuk memberikan hadiah lain (giring harus menunggu elf untuk kembali sebelum pergi ke rumah berikutnya), mengambil empat detik lagi

4. (18-an) Rumah keempat tidak dalam semangat Natal, sehingga memiliki 0 orang nakal dan 0 orang baik, dan dilewati

5. (18-an) Rumah kelima memiliki 4 orang nakal dan 7 orang baik. Ini jadi sedikit rumit ...

   I. Kesembilan elf pergi untuk mengirimkan tiga hadiah batu bara (tinggalkan t + 0, kembalikan t + 5) II. Setelah 5s, mereka semua kembali ke giring, dan tiga dari mereka pergi untuk memberikan hadiah terakhir batubara (meninggalkan t + 5, mengembalikan t + 10) sementara enam lainnya pergi untuk memberikan tiga hadiah bagus (meninggalkan t + 5s, kembalikan t + 9s).

   AKU AKU AKU. Setelah empat detik, enam elf kembali dan pergi untuk memberikan tiga hadiah bagus lagi (tinggalkan t + 9, kembalikan t + 13).

   IV. Satu detik setelah mereka pergi, tiga elf yang mengirimkan hadiah batu bara kembali, dan dua dari mereka pergi untuk memberikan hadiah bagus terakhir (cuti + 10, kembali t + 14)

6. (18 + 14 = 32 detik ) Santa selesai mengirimkan hadiah ke wilayah itu.

Seperti yang dapat kita lihat, dibutuhkan Santa total 32 detik untuk mengirimkan hadiah ke wilayah ini. Tapi itu adalah versi salah satu peta Santa yang terlalu disederhanakan. Biasanya, peta Santa memiliki banyak garis, dan berada dalam bentuk persegi agar lebih sesuai dalam daftar. Peta normal mungkin terlihat seperti ini (a \ndi akhir setiap baris)

1*2+*+*4+1*
2*4+3*+1*6+*
*+*+4*2+1*1
*4+*3+1*+2*3
3*10+2*+*5+*

Dengan 26 elf (atau jumlah yang lebih tinggi), itu akan membutuhkan Santa 71 detik .
Dengan 20 elf , dibutuhkan Santa 76 detik .
Dengan 15 elf , dibutuhkan Santa 80 detik .
Dengan 3 elf , dibutuhkan waktu Santa 288 detik .
Dengan 2 elf (atau jumlah yang lebih rendah), itu tidak mungkin.

Oh, dan satu hal lagi - urutan di mana elf mengirim hadiah penting (karena perbedaan waktu pengiriman hadiah nakal / orang baik), jadi kode Anda harus selalu menampilkan jumlah waktu paling sedikit yang bisa diambil oleh elf untuk mengirimkan hadiah.

Tantangan

Bantu Santa menentukan berapa lama waktu yang dibutuhkan sejumlah peri untuk mengirimkan hadiah.

Rumah

• Sebuah rumah diwakili oleh a *
• Rumah dibagi oleh +
• Angka di sebelah kiri rumah melambangkan jumlah orang nakal (tidak ada angka berarti 0)
• Angka di sebelah kanan melambangkan jumlah orang baik (tidak ada angka berarti 0)
• Mungkin ada baris baru ( \n) di input, yang juga harus ditangani sebagai pemisahan

Peri

• Santa membutuhkan bantuan dari tiga elf untuk orang-orang nakal (batu bara jauh lebih berat daripada hadiah), dan elf-elf ini butuh waktu lima detik ^* untuk mengirimkan hadiah
• Santa membutuhkan bantuan dari dua elf untuk orang-orang baik, dan elf ini membutuhkan waktu empat detik ^* untuk mengirimkan hadiah
• Jika tidak ada nomor di kedua sisi rumah, Santa tidak akan mengunjungi rumah itu, dan karenanya tidak akan memakan waktu (orang-orang yang tidak dalam semangat Natal bahkan tidak pantas mendapatkan batu bara)

Santa

• Santa harus memberikan hadiah ke rumah-rumah satu per satu
• Santa tidak dapat pindah ke rumah berikutnya sampai semua elf kembali ke giring dan semua hadiah telah dikirim ke rumah itu (kita tidak ingin meninggalkan elf di belakang, sekarang bukan?)
• Giring Santa tidak menghabiskan waktu bepergian dari rumah ke rumah (Lagi-lagi, untuk alasan yang tidak bisa saya bagikan)

Apa yang harus dilakukan

Diberi peta rumah dan sejumlah peri, cetak berapa lama waktu yang dibutuhkan Santa untuk mengirimkan hadiah ke rumah-rumah di peta.

_{* (Saya mungkin tidak membagikan jumlah waktu yang dibutuhkan elf untuk mengirimkan hadiah. Saya tidak dapat mengkonfirmasi atau menyangkal bahwa waktu yang termasuk dalam tantangan ini benar)}

Aturan

• Ada dua input - peta dan jumlah elf. Input dapat diambil sebagai argumen untuk suatu fungsi, atau dari STDIN atau yang setara. Jika mengambil dua input tidak mungkin dalam bahasa Anda, maka dan hanya setelah itu Anda dapat menerima dua input sebagai string input tunggal, dibatasi oleh beberapa karakter yang biasanya tidak dalam input (bukan salah satu +*\natau 0-9- string input tidak dapat ambigu) mis ,.
• Jumlah elf akan selalu berupa bilangan bulat non-negatif (0 valid)
• Outputnya bisa berupa nilai balik suatu fungsi, atau dicetak ke STDOUT atau setara. Jika Santa tidak mungkin mengirimkan hadiah ke wilayah tertentu dengan jumlah peri tertentu, Anda harus menampilkan angka negatif yang konsisten, atau pesan yang konsisten tanpa angka di dalamnya
• Semua yang dicetak ke STDERR akan diabaikan, jadi Anda tidak boleh mencetak hasil atau pesan kesalahan ke STDERR
• Program Anda tidak dapat crash karena jumlah elf yang tidak valid untuk suatu wilayah
• Hasilnya seharusnya hanya jumlah total waktu yang dibutuhkan Santa untuk mengirimkan hadiah dengan jumlah elf yang diberikan.
• Keluaran harus selalu menjadi jumlah waktu paling sedikit yang dibutuhkan elf untuk mengirimkan hadiah
• Input hanya akan berisi angka, +, *, dan baris \n(kecuali jika Anda menentukan karakter lain yang input akan mencakup jika bahasa Anda tidak dapat mengambil dua input _{(lihat aturan pertama)} )
• Celah standar berlaku

Uji Kasus

"1*1", 5 elves => 5
"1*1", 3 elves => 9
"1*2", 7 elves => 5
"1*2", 5 elves => 10
"1*2", 3 elves => 13
"2*1", 8 elves => 5
"2*1", 5 elves => 9
"2*1", 3 elves => 14
"1*" , 3 elves => 5
"1*" , 2 elves => (error message)
"*1" , 2 elves => 4
"*1" , 0 elves => (error message)
"*"  , 0 elves => 0

"1*1+1*1",   5 elves => 10
"1*1+1*1",   3 elves => 18
"1*1+*+1*1", 3 elves => 18
"1*2+2*1",   8 elves => 10
"1*2+2*1",   7 elves => 14
"1*2+2*1",   6 elves => 18
"1*2+2*1",   3 elves => 27
"1*2+2*1",   2 elves => (error message)
"*+*+*+*",   2 elves => 0
"*+*+*+*",   0 elves => 0

"1*3+2*+*5+*+4*7", 9 elves => 32

_{(Mudah-mudahan saya mendapatkan semua itu dengan benar)}

Mencetak gol

Santa menghabiskan setiap hari selalu melihat banyak hal - semua hadiah yang akan dia berikan, semua elf yang dia miliki, semua rumah yang dia berikan hadiah untuk ... Untuk Santa, hadiah Natal terbaik akan menjadi bisa melihat sedikit dari sesuatu. Karena alasan ini, pengiriman terpendek dalam byte akan menang .

Papan peringkat

Ini adalah Stack Snippet yang menghasilkan leaderboard dan ikhtisar pemenang berdasarkan bahasa.

Untuk memastikan jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama menggunakan templat Penurunan harga berikut

## Language Name, N bytes

Di mana N adalah ukuran, dalam byte, dari kiriman Anda

Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (misalnya, mengecoh skor lama, atau menyertakan bendera dalam jumlah byte), pastikan saja skor aktual adalah angka terakhir di tajuk Anda

## Language Name, <s>K</s> X + 2 = N bytes

var QUESTION_ID=151568;var OVERRIDE_USER=20634;function answersUrl(e){return"http://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"http://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>

Ruby , 433 400 byte

Nah, yang ini memang susah, karena ternyata penjadwalan elf itu NP susah.

Juga, mohon bersikap baik, ini adalah pengiriman pertama saya, jadi saya mungkin telah melewatkan beberapa optimasi yang jelas:

->e,h{h.split(/\+|\n/).map{|h|n,g=h.split(?*).map(&:to_i)+[0,0];return-1if(g>0&&e<2)||(n>0&&e<3);([[3,5]]*n+[[2,4]]*g).permutation.map{|j|c=[0]*e;j.map{|q|w,y=q;k=l=0;r=c.map{|x|a=b=0;c[k..e].map{|r|r<=x ?a+=1:break};(t=k+=1).times{c[t-=1]<=x ?b+=1:break};[a,b]};d=r.inject([]){|v,x|v<<l if x[0]>=w;l+=1;v}.min{|a,b|c[a]<=>c[b]};b=d-r[d][1]+1;z=c[d]+y;(b..(b+w-1)).map{|x|c[x]=z}};c.max}.min||0}.sum}

Cobalah online!

Saya awalnya memiliki test case yang lebih lama, tetapi karena saya mengulangi semua permutasi yang mungkin untuk penjadwalan dalam beberapa kasus yang dibutuhkan lama, jadi saya menghapusnya.

Java (OpenJDK 8) , 344 byte

Penjadwalan elf lebih sulit dari yang saya kira jadi ini butuh sedikit waktu, dan cukup lama.

Meskipun begitu, ini jelas merupakan tantangan favorit saya untuk kode golf!

(e,d)->{int r=0,x,y,c,p,b,g,m;for(String h:d[0].split("\\+")){d=h.split("\\*",-1);b=new Byte("0"+d[0]);g=new Byte("0"+d[1]);m=-1>>>1;for(y=1;y<=e/3&(x=(e-y*3)/2)>0;c=b/y+(b%y++<1?0:1),p=g/x+(g%x<1?0:1),x=c*5>p*4?c*5:p*4,m=x<m?x:m);for(y=0;b+g>0;b-=c,g-=p){c=e/3<b?e/3:b;x=(e-c*3)/2;p=x<g?x:g;if(c+p<1)return-1;y+=c>0?5:4;}r+=m<y?m:y;}return r;}

Cobalah online (dengan semua tes)!

Penjelasan;

Persiapkan dirimu: Itu panjang

    int r=0,x,y,c,p,b,g,m;               // Define all the variables I need

    for(String h:d[0].split("\\+")){     // Split houses on '+' and loop through them

        d=h.split("\\*",-1);             // Split the current house on '*' using the limit
                                         // to preserve empty strings.

        b=new Byte("0"+d[0]);            // Parse the naughty (b) and nice (g) people
        g=new Byte("0"+d[1]);

        m=-1>>>1;                        // Initialise minimum time as max integer using
                                         // overflow

        for(y=1;y<=e/3&(x=(e-y*3)/2)>0;  // For each number of elves that can concurrently
                                         // deliver coal, and still leave enough elves to
                                         // deliver presents

            c=b/y+(b%y++<1?0:1),         // Determine the number of runs needed to deliver
                                         // all coal using this number of elves

            p=g/x+(g%x<1?0:1),           // Determine the number of runs needed to deliver
                                         // all presents using this number of elves

            x=c*5>p*4?c*5:p*4,           // Get the maximum time required for the
                                         // delivery of coal or presents

            m=x<m?x:m);                  // If this is less than the current minimum time,
                                         // set it as the minimum time


        for(y=0;b+g>0;b-=c,g-=p){        // While there are still people to deliver to;

            c=e/3<b?e/3:b;               // Determine the max amount of coal to deliver

            x=(e-c*3)/2;                 // Determine how many presents can be
                                         // delivered with the remaining elves.

            p=x<g?x:g;                   // If this number is more than nice people
                                         // remaining, just use the nice people remaining

            if(c+p<1)return-1;           // If no presents can be delivered, return the
                                         // error code (-1)

            y+=c>0?5:4;                  // Increase the time by 5 if coal was
                                         // delivered, and 4 if only presents

        }                                // At the end of each loop (see above)
                                         // remove the presents and coal delivered
                                         // from the number of naughty and nice houses

        r+=m<y?m:y;                      // Increment the total time by which ever
                                         // is smaller of the calculated times
    }
    return r;                            // Return the total time

NB: Jawaban ini tergantung pada koreksi saya pada kasus uji yang benar