Оптимизировать мой порядок крыльев

17

В этом твите перечислены возможные заказы на крылья китайского ресторана 1 :

Крылья меню

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

Вызов

Если задано целое число, большее или равное 4 , ваша задача - вернуть один возможный заказ, который минимизирует цену (в целом самая дешевая) и количество сделок.

пример

Если бы я заказал 100 Wings, оказалось, что лучшая сделка обойдется в $111.20 . Однако есть несколько заказов, которые будут стоить эту сумму, а именно:

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

Поскольку первый заказ будет использовать наименьшее количество сделок ( 2 ), результат будет[50,50] .

правила

  • На входе будет некоторое целое число n4
  • Вывод будет список / массив / ... размеров заказа, которые в сумме до n и минимизируют цену заказа
    • Вы можете вернуть все возможные заказы

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)

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


1: Вы можете найти данные как CSV здесь .

ბიმო
источник
3
Вопрос в том, кто заказывает 200 или даже 100 крыльев? ...
Эрик Outgolfer
2
@Quintec: Почему вам нужно больше тестов?
ბიმო
1
Два ответа неверно истолковали требования, так как нужно было только минимизировать цену. Поскольку минимизация цены и количества сделок неоднозначна (самая низкая цена доступна для способов с наименьшим количеством сделок или минимальное количество сделок доступна для способов с наименьшей ценой), стоит отредактировать требование, чтобы оно было более явным
Трихоплакс
1
Я замечаю, что для цена определяется как 1n23120(68n3)25<n<=5025n25n<297080125

Ответы:

7

JavaScript (ES6), 123 байта

Возвращает заказ в виде строки через пробел.

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):''

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

Как?

n

n>128n=125

125n129n125

125<n<1294 крыльев, что невозможно.

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
источник
4

JavaScript (Node.js) , 112 108 106 105 байт

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):''

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

Оптимизировано из ответа Арно

Различия

  • 51≤n≤53 объединяется в 31≤n≤50 (8 байт)
  • Переписать растровое изображение (сохранение 3 байта)
  • Переставить некоторую логику ( 4 6 7 байт сохранено)
l4m2
источник
2

Retina 0.8.2 , 160 155 байт

.+
$*
{`\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

.+
$*

Преобразовать в одинарный.

{`

Повторяйте до тех пор, пока не будет куплено больше сделок.

{`\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

n

Сделки приобретаются на следующих условиях:

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

Купите 80 крыльев, если это оставляет 0, 6, 9, 12, 15, 18, 25 или 28 крыльев.

1{70}$

Купите 70 крыльев, если это все, что нам нужно.

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

Купите 9 крыльев, если осталось 15 или 40 крыльев.

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

Купите 30, 35, 40 или 45 крыльев, если это все, что нам нужно.

1{26,29}$

Купите 26, 27, 28 или 29 крыльев, если это все, что нам нужно.

1{4,23}$

Купите от 4 до 23 крыльев, если это все, что нам нужно.

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

Купите 125, 50 или 25 крыльев, если мы можем, и если мы еще можем купить больше крыльев точно. Обратите внимание, что у нас есть эти варианты в конце чередования, так что точные покупки проверяются в первую очередь.

Нил
источник