Ce tweet répertorie les commandes possibles pour les ailes d'un restaurant chinois ¹ :

Lors de la commande de pizza, je calcule généralement quelle taille me donne le meilleur rapport pizza-prix qui est un calcul simple. Cependant, minimiser le prix d'une commande dans ce restaurant n'est pas une tâche aussi simple, alors j'aimerais être prêt pour ma prochaine commande là-bas.

Défi

Étant donné un nombre entier supérieur ou égal à $4$ , votre tâche consiste à retourner une commande possible qui minimise le prix (globalement le moins cher) et le nombre d'offres.

Exemple

Si je devais commander $100$ Wings, il s'avère que la meilleure affaire coûtera 111,20 $$111.20$ . Cependant, plusieurs commandes coûteront ce montant, à savoir:

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

Étant donné que la première commande utilisera le moins d'offres ( $2$ ), le résultat sera [50,50].

Règles

• L'entrée sera un entier $n \geq 4$
• La sortie sera une liste / tableau / ... des tailles de commande qui résument jusqu'à $n$ et minimisent le prix de la commande
  • vous pouvez choisir de retourner toutes les commandes possibles

Cas de test

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)

Remarque: Ces tests répertorient toutes les sorties possibles, y compris le prix, vous n'êtes obligé d'en sortir qu'une et vous n'êtes pas obligé de sortir le prix!

_{1: Vous pouvez trouver les données au format CSV ici .}

JavaScript (ES6), 123 octets

Renvoie l'ordre sous forme de chaîne séparée par des espaces.

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

Essayez-le en ligne!

Comment?

$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 octets

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

Essayez-le en ligne!

Optimisé à partir de la réponse d'Arnauld

Différences

• 51≤n≤53 est fusionné en 31≤n≤50 (sauvegarde de 8 octets)
• Réécrire le bitmap (sauvegarde de 3 octets)
• Réorganiser une logique ( 4 6 7 octets enregistrés)

0.8.2 Retina , 160 155 bytes

.+
$*
{`\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$ lui-même. Utilise l'algorithme de @ Arnauld. Edit: économisé 5 octets en achetant 95 ailes en 80 + 15 au lieu de 50 + 45. Explication:

.+
$*

Convertissez en unaire.

{`

Répétez jusqu'à ce qu'aucune autre offre ne puisse être achetée.

{`\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,$&

Trouvez un moyen d'acheter des offres et capturez et dupliquez l'une des offres.

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

$n$ .

Les offres sont achetées dans les conditions suivantes:

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

Achetez 80 ailes si cela laisse 0, 6, 9, 12, 15, 18, 25 ou 28 ailes.

1{70}$

Achetez 70 ailes si c'est tout ce dont nous avons besoin.

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

Achetez 9 ailes si cela laisse 15 ou 40 ailes.

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

Achetez 30, 35, 40 ou 45 ailes si c'est tout ce dont nous avons besoin.

1{26,29}$

Achetez 26, 27, 28 ou 29 ailes si c'est tout ce dont nous avons besoin.

1{4,23}$

Achetez 4 à 23 ailes si c'est tout ce dont nous avons besoin.

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

Achetez 125, 50 ou 25 ailes si nous le pouvons et si nous pouvons toujours acheter plus d'ailes exactement. Notez que nous avons ces options à la fin de l'alternance afin que les achats exacts soient testés en premier.