Optimalkan pesanan sayap saya

17

Tweet ini mencantumkan kemungkinan pesanan untuk Wings of a Chinese restaurant 1 :

Menu sayap

Saat memesan Pizza, saya biasanya menghitung ukuran apa yang memberi saya rasio harga Pizza terbaik yang merupakan perhitungan sederhana. Namun meminimalkan harga pesanan di restoran ini bukan tugas yang mudah, jadi saya ingin bersiap untuk pesanan berikutnya di sana.

Tantangan

Diberikan bilangan bulat lebih besar atau sama dengan 4 , tugas Anda adalah mengembalikan satu kemungkinan pesanan yang meminimalkan harga (termurah keseluruhan) dan jumlah transaksi.

Contoh

Jika saya memesan 100 Wings, ternyata tawaran terbaik akan dikenakan biaya $111.20 . Namun ada beberapa pesanan yang akan dikenakan biaya sebesar itu, yaitu:

[50,50],[25,25,50],[25,25,25,25]

Karena pesanan pertama akan menggunakan jumlah penawaran paling sedikit ( 2 ) hasilnya akan[50,50] .

Aturan

  • Input akan berupa bilangan bulat n4
  • Output akan berupa daftar / larik / ... ukuran pesanan yang berjumlah hingga n dan meminimalkan harga pesanan
    • Anda dapat memilih untuk mengembalikan semua pesanan yang mungkin

Testcases

4 -> [4]  (4.55)
23 -> [23]  (26.10)
24 -> [6,18],[9,15],[12,12]  (27.20)
31 -> [6,25]  (34.60)
32 -> [4,28],[6,26],[7,25]  (35.75)
33 -> [4,29],[5,28],[6,27],[7,26],[8,25]  (36.90)
34 -> [6,28],[9,25]  (38.00)
35 -> [35]  (39.15)
125 -> [125]  (139.00)
200 -> [25,50,125]  (222.40)
201 -> [26,50,125]  (223.55)
250 -> [125,125]  (278.00)
251 -> [26,50,50,125]  (279.15)
418 -> [15,28,125,125,125],[18,25,125,125,125]  (465.20)
1001 -> [26,50,50,125,125,125,125,125,125,125]  (1113.15)
12345 -> [15,80,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125],[25,70,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125],[45,50,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125]  (13728.10)

Catatan: Testcases ini mencantumkan semua kemungkinan output termasuk harga, Anda hanya diharuskan untuk output satu dan Anda tidak diharuskan untuk output harga!


1: Anda dapat menemukan data sebagai CSV di sini .

ბიმო
sumber
3
Pertanyaan sebenarnya adalah, siapa yang memesan 200 atau bahkan 100 sayap? ...
Erik the Outgolfer
2
@ Quintec: Mengapa, Anda perlu lebih banyak testcases?
ბიმო
1
Dua jawaban telah salah menafsirkan persyaratan, karena hanya perlu meminimalkan harga. Karena meminimalkan harga dan jumlah penawaran bersifat ambigu (harga terendah yang tersedia dari cara-cara dengan jumlah penawaran terendah, atau jumlah penawaran terendah yang tersedia dari cara-cara dengan harga terendah), ada baiknya mengedit persyaratan untuk menjadi lebih eksplisit
trichoplax
1
Saya perhatikan bahwa untuk harga diberikan oleh 1n23, sementara harga untuk25<n<=50dapat dibagi menjadi25dann-25(untukn<29Anda tidak dapat membelinya secara terpisah tetapi formula masih memberikan nilai yang sesuai). 70,80dan125juga dapat diturunkan dari nilai sebelumnya, jadi jika Anda bisa menggunakannya mereka akan mengurangi jumlah penawaran. Nilai-nilai lainnya tidak ekonomis. 120(68n3)25<n<=5025n25n<297080125
Neil

Jawaban:

7

JavaScript (ES6), 123 byte

Mengembalikan urutan sebagai string yang dipisahkan oleh spasi.

f=n=>n?(x=n>128|n==125?125:n>50?n<54?25:n-70?302256705>>n-80&n>79&n<109?80:50:n:n-24&&n-49?n<31|n%5<1?n:25:9)+' '+f(n-x):''

Cobalah online!

Bagaimana?

Diberi nomor n sayap, kami rekursif menerapkan strategi berikut.

Nilai tinggi: n>128 atau n=125

Untuk nilai tinggi, opsi terbaik kami adalah membeli 125 sayap. Jadi itulah yang kami lakukan selama n lebih besar dari atau sama dengan 129 atau ketika n persis sama dengan 125 .

Kita tidak bisa melakukan itu untuk 125<n<129 karena kita akan dibiarkan dengan kurang dari 4 sayap untuk membeli, yang tidak mungkin.

Nilai rendah: n<31

n<31n=242×1218+615+99

31n50

25

  • n5
  • n=4940+928+219

51n53

504252×26n=5225+27

54n128n125

50

  • n=70
  • n{80,86,89,92,98,105,108}8080108

    10010000001000001001001000001(2)=302256705(10)

Arnauld
sumber
4

JavaScript (Node.js) , 112 108 106 105 byte

f=n=>n?(x=n>128|n==125?125:n>53&n!=70?1629>>n/3+6&n<99==n%3/2?80:50:~n%25?n>30&&n%5?25:n:9)+' '+f(n-x):''

Cobalah online!

Dioptimalkan dari jawaban Arnauld

Perbedaan

  • 51≤n≤53 digabung menjadi 31≤n≤50 (hemat 8 byte)
  • Tulis ulang bitmap (hemat 3 byte)
  • Susun ulang beberapa logika ( 4 6 7 byte disimpan)
l4m2
sumber
2

Retina 0.8.2 , 160 155 byte

.+
$*
{`\b(1{80}(?=((111){2,6}|1{25}|1{28})?$)|1{70}$|1{9}(?=.{15}$|.{40}$)|(1{5}){6,9}$|1{26,29}$|1{4,23}$|1{125}|1{50}|1{25})+$
$1,$&
(1+),\1(1*)$
$.1,$2

nn

.+
$*

Konversikan ke unary.

{`

Ulangi sampai tidak ada lagi transaksi yang dapat dibeli.

{`\b(1{80}(?=((111){2,6}|1{25}|1{28})?$)|1{70}$|1{9}(?=.{15}$|.{40}$)|(1{5}){6,9}$|1{26,29}$|1{4,23}$|1{125}|1{50}|1{25})+$
$1,$&

Temukan cara untuk membeli penawaran dan menangkap serta menggandakan salah satu penawaran.

(1+),\1(1*)$
$.1,$2

n

Penawaran dibeli dengan ketentuan sebagai berikut:

1{80}(?=((111){2,6}|1{25}|1{28})?$)

Beli 80 sayap jika tersisa 0, 6, 9, 12, 15, 18, 25 atau 28 sayap.

1{70}$

Beli 70 sayap jika hanya itu yang kita butuhkan.

1{9}(?=.{15}$|.{40}$)

Beli 9 sayap jika itu menyisakan 15 atau 40 sayap.

(1{5}){6,9}$

Beli 30, 35, 40 atau 45 sayap jika hanya itu yang kami butuhkan.

1{26,29}$

Beli 26, 27, 28 atau 29 sayap jika hanya itu yang kita butuhkan.

1{4,23}$

Beli 4 hingga 23 sayap jika itu yang kita butuhkan.

1{125}|1{50}|1{25}

Beli 125, 50, atau 25 sayap jika kita bisa dan jika kita masih bisa membeli lebih banyak sayap dengan tepat. Perhatikan bahwa kami memiliki opsi ini di akhir pergantian sehingga pembelian yang tepat diuji terlebih dahulu.

Neil
sumber