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

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

Вызов

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

пример

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

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

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

правила

• На входе будет некоторое целое число $n \geq 4$
• Вывод будет список / массив / ... размеров заказа, которые в сумме до $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 здесь .}

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>128$$n=125$

$125$$n$$129$$n$$125$

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

$n<31$

$n<31$$n=24$$2\times 12$$18+6$$15+9$$9$

$31 \le n \le 50$

$25$

• $n$$5$
• $n=49$$40+9$$28+21$$9$

$51 \le n \le 53$

$50$$4$$25$$2\times26$$n=52$$25+27$ такая же хорошая.)

$54 \le n \le 128$$n \neq 125$

$50$

• $n=70$

• $n$$\{80,86,89,92,98,105,108\}$$80$$80$$108$

  $$10010000001000001001001000001_{(2)} = 302256705_{(10)}$$

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 байт сохранено)

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

$n$$n$

.+
$*

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

{`

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

{`\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 крыльев, если мы можем, и если мы еще можем купить больше крыльев точно. Обратите внимание, что у нас есть эти варианты в конце чередования, так что точные покупки проверяются в первую очередь.