Au Canada, le sou n'est plus distribué. Les paiements en espèces sont arrondis aux 5 cents les plus proches.

L'argent peut être économisé en fractionnant les achats. Par exemple, deux articles de 1,02 $ coûtent 2,04 $, ce qui arrondit à 2,05 $, mais lors de l'achat des articles dans des achats séparés, chaque prix arrondit à 1,00 $ pour un total de 2,00 $. Cependant, lors de l'achat de deux articles à 1,03 $ chacun, il est préférable de les acheter en un seul achat.

Une autre façon d'économiser de l'argent consiste à utiliser une carte de crédit lorsque l'arrondi est défavorable, car les paiements par crédit ne sont pas arrondis. Si nous voulons deux articles 1,04 $, le prix total arrondira à 2,10 $, quelle que soit la façon dont nous répartissons les achats. Par conséquent, nous devons payer ces articles avec une carte de crédit.

Écrivez une fonction ou un programme qui accepte une liste de prix des articles sous forme d'entiers en cents et affiche le prix total le plus bas possible (en cents) pour ces articles qui peut être atteint par une séquence d'achats, chacun en espèces ou par crédit.

Le code le plus court gagne.

Cas de test

[] : 0
[48] : 48
[92, 20] : 110
[47, 56, 45] : 145
[55, 6, 98, 69] : 225
[6, 39, 85, 84, 7] : 218
[95, 14, 28, 49, 41, 39] : 263
[92, 6, 28, 30, 39, 93, 53] : 335
[83, 33, 62, 12, 34, 29, 18, 12] : 273
[23, 46, 54, 69, 64, 73, 58, 92, 26] : 495
[19, 56, 84, 23, 20, 53, 96, 92, 91, 58] : 583
[3, 3, 19, 56, 3, 84, 3, 23, 20, 53, 96, 92, 91, 58, 3, 3] : 598
[2, 3, 4, 4, 4, 4, 4] : 19

Ruby, 119 105 caractères (93 corps)

def f s
a,b,c,d=(1..4).map{|i|s.count{|x|x%5==i}}
s.reduce(0,:+)-a-(c-m=c>d ?d:c)/2-2*(b+m+(d-m)/3)
end

Deux caractères peuvent être enregistrés si l'algorithme est autorisé à planter lorsqu'il est alimenté par une liste de courses vide.

GolfScript (54 caractères)

~]4,{){\5%=}+1$\,,}%~.2$>$:m- 3/m+@+2*@@m- 2/++~)+{+}*

Il s'agit d'un programme qui prend l'entrée de stdin en tant que valeurs séparées par des espaces. Un caractère pourrait être enregistré en forçant le format d'entrée à être à la place un tableau GolfScript.

Cas de test en ligne

L'astuce la plus intéressante est .2$>$pour un minopérateur non destructif .

Mon analyse des mathématiques est essentiellement la même que celle de Jan et Ray: compte tenu des valeurs du module 5, la seule économie concerne les transactions valant 1 ou 2. L'option de carte de crédit signifie que nous ne arrondissons jamais. Donc, un article qui coûte 5n + 2 cents ne peut pas bénéficier du bundling; un article ne vaut pas non plus 5n + 1 cents (car la combinaison de deux économies de 1 cent en une économie de 2 cents ne donne aucun avantage). 0 est l'identité additive, donc les seuls cas intéressants impliquent des valeurs de 3 et 4. 3+3 = 1et 3+4 = 4+4+4 = 2; si nous avons 3 s mixtes et 4s alors nous en préférant optimiser 3+4plus 3+3(strictement mieux) ou 4+4+4(équivalent).

C ++: 126 caractères

int P(int*m,int i){int t=0,h=0,d;while(i>-1){d=m[i]%5;t+=m[i--];d<3?t-=d:d==4?h++,t-=2:h--;}h<0?t+=h/2:t+=(h-h/3)*2;return t;}

Bienvenue pour donner des conseils pour mettre ce programme devient plus court.Voici le programme de test, compilez avec le compilateur tdm-gcc 4.7.1 et exécutez-le normalement.

#include<iostream>
using namespace std;

//m[i]表示单个商品的价格,t表示所有商品总价格,
//d为单个商品价格取模后的值,h为单个商品价格取模后值为3的个数,
//f为单个商品价格取模后值为4的个数
int P(int*m,int i){int t=0,h=0,d;while(i>-1){d=m[i]%5;t+=m[i--];d<3?t-=d:d==4?h++,t-=2:h--;}h<0?t+=h/2:t+=(h-h/3)*2;return t;}

int main() {
int p1[1]={48};
int p2[2]={92,20};
int p3[3]={47,56,45};
int p4[4]={55,6,98,69};
int p5[5]={6,39,85,84,7};
int p6[6]={95,14,28,49,41,39};
int p7[7]={92,6,28,30,39,93,53};
int p8[8]={83,33,62,12,34,29,18,12};
int p9[9]={23,46,54,69,64,73,58,92,26};
int p10[10]={19,56,84,23,20,53,96,92,91,58};
int p11[10]={1,2,3,4,5,6,7,8,9,10};
cout<<P(p1,0)<<endl
    <<P(p2,1)<<endl
    <<P(p3,2)<<endl
    <<P(p4,3)<<endl
    <<P(p5,4)<<endl
    <<P(p6,5)<<endl
    <<P(p7,6)<<endl
    <<P(p8,7)<<endl
    <<P(p9,8)<<endl
    <<P(p10,9)<<endl
    <<P(p11,9)<<endl;

return 0;
}

R 143

function(x)min(sapply(rapply(partitions::listParts(length(x)),
                             function(i)min(sum(x[i]),5*round(sum(x[i])/5)),h="l"),
                      function(x)sum(unlist(x))))

Tests (où Pest un alias pour le code ci-dessus)

> P(c(48))
[1] 48
> P(c(92, 20))
[1] 110
> P(c(47, 56, 45))
[1] 145
> P(c(55, 6, 98, 69))
[1] 225
> P(c(6, 39, 85, 84, 7))
[1] 218
> P(c(95, 14, 28, 49, 41, 39))
[1] 263
> P(c(92, 6, 28, 30, 39, 93, 53))
[1] 335
> P(c(83, 33, 62, 12, 34, 29, 18, 12))
[1] 273
> P(c(23, 46, 54, 69, 64, 73, 58, 92, 26))
[1] 495
> P(c(19, 56, 84, 23, 20, 53, 96, 92, 91, 58))
[1] 583

Mathematica 112 126 167 157 157

Edit : les cas de {3, 3} et {4,4,4} sont désormais traités grâce à Peter Taylor et à cardboard_box.

n_~g~o_ := {a___, Sequence @@ n, b___} :> {a, b, o};
f@s_ := Tr@Join[#[[2]], Sort@#[[1]] //. {1 -> 0, 2 -> 0, g[{3, 4}, 5], g[{3, 3}, 5], 
   g[{4, 4, 4}, 10]}] &[Transpose[{m = Mod[#, 5], # - m} & /@ s]]

Remarque: les non-achats (cas de test n ° 1) sont entrés comme f[{0}].

Comment ça fonctionne

1. Pour chaque article, le plus grand multiple de 5 de moins que le prix respectif sera payé quel que soit le mode de paiement. (Pas de contournement.)
2. Les restes de Mod[n, 5]sont ensuite traités: les 1 et les 2 deviennent des 0. Les zéros restent inchangés.
3. Chaque paire {3, 4} -> {5}; ensuite chaque paire {3, 3} -> {5}; puis le triple, {4,4,4} -> {10}, le cas échéant.
4. Les 4 autres, le cas échéant, restent inchangés (payés par carte de crédit).
5. Multiples originaux de 5 additionnés de restes qui ont été modifiés (ou non) aux étapes (2) à (4).

Essai

a12ajuste pour {3,3} a13ajuste pour {4,4,4}

a1={0};
a2={48};
a3={92,20};
a4={47,56,45};
a5={55,6,98,69} ;
a6={6,39,85,84,7};
a7={95,14,28,49,41,39};
a8={92,6,28,30,39,93,53};
a9={83,33,62,12,34,29,18,12};
a10={23,46,54,69,64,73,58,92,26};
a11={19,56,84,23,20,53,96,92,91,58};
a12={3,3,19,56,3,84,3,23,20,53,96,92,91,58,3,3};
a13={2,3,4,4,4,4,4};

f /@ {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13}

{0, 48, 110, 145, 225, 218, 263, 335, 273, 495, 583, 598, 19}

Python 3 (115 caractères)

m=eval(input());t=a=b=0
for v in m:d=v%5;t+=v-d*(d<3);a+=d==3;b+=d==4
d=min(a,b);a-=d;b-=d;print(t-d*2-a//2-b//3*2)

Python 2 (106 caractères)

m=input();t=a=b=0
for v in m:d=v%5;t+=v-d*(d<3);a+=d==3;b+=d==4
d=min(a,b);a-=d;b-=d;print t-d*2-a/2-b/3*2

APL, 58 caractères

{a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}

Le programme est essentiellement une traduction directe de la solution Ruby de Jan Dvorak .

      {a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}⍬
0
      {a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}95 14 28 49 41 39
263
      {a b c d←+/(⍳4)∘.=5|⍵⋄(+/⍵)-a-(⌊2÷⍨c-m)-2×b+m+⌊3÷⍨d-m←c⌊d}19 56 84 23 20 53 96 92 91 58
583

⍬ est le vecteur vide.

Julia 83C

C=L->let
w,z,x,y=map(i->[i==x%5for x=L]|sum,1:4)
L|sum-(x+2w+3min(x,y)+4z)>>1
end

Explication:

En un seul achat, vous pouvez économiser 2 centimes au maximum. Donc, si vous avez une combinaison qui peut vous faire économiser 2 cents, achetez-la de cette façon et ce sera optimal . Par exemple, si vous avez des xarticles avec le prix 3 (mod 5) et des yarticles avec le prix 4 (mod 5), vous pouvez créer un min(x, y)nombre de (3, 4) paires, ce qui vous fait économiser des 2 min(x, y)cents. Ensuite, vous utilisez les 3 autres, le cas échéant, pour vous faire économiser des max(0, x-min(x,y)) / 2cents. Cela peut également être calculé par(max(x,y)-y)/2

w = sum(1 for p in prices if p % 5 == 1)
z = sum(1 for p in prices if p % 5 == 2)
x = sum(1 for p in prices if p % 5 == 3)
y = sum(1 for p in prices if p % 5 == 4)

ans = sum(prices) - (w + 2 z + 2 min(x, y) + div(max(x, y) - y, 2))
    = sum(prices) - (2w + 4z + 4 min(x, y) + x + y - min(x, y) - y) `div` 2
    = sum(prices) - (2w + 4z + 3 min(x, y) + x) `div` 2

Éditer

Cette solution est fausse.