In Kanada wird der Penny nicht mehr in Umlauf gebracht. Barzahlungen werden auf die nächsten 5 Cent gerundet.

Durch die Aufteilung der Einkäufe kann Geld gespart werden. Zum Beispiel kosten zwei Artikel im Wert von 1,02 US-Dollar 2,04 US-Dollar, was sich auf 2,05 US-Dollar aufrundet. Wenn Sie die Artikel jedoch in separaten Käufen kaufen, wird jeder Preis auf 1,00 US-Dollar gerundet, was einem Gesamtbetrag von 2,00 US-Dollar entspricht. Wenn Sie jedoch zwei Artikel zu einem Preis von jeweils 1,03 USD kaufen, ist es besser, sie in einem einzigen Einkauf zu kaufen.

Eine andere Möglichkeit, Geld zu sparen, ist die Verwendung einer Kreditkarte, wenn die Rundung ungünstig ist, da Kreditzahlungen nicht gerundet werden. Wenn wir zwei Artikel im Wert von 1,04 USD haben möchten, wird der Gesamtpreis auf 2,10 USD aufgerundet, unabhängig davon, wie wir die Käufe aufgeteilt haben. Daher sollten wir diese Artikel mit einer Kreditkarte bezahlen.

Schreiben Sie eine Funktion oder ein Programm, das eine Liste der Artikelpreise als Ganzzahl in Cent akzeptiert und den niedrigstmöglichen Gesamtpreis (in Cent) für die Artikel ausgibt, die durch eine Abfolge von Einkäufen entweder in bar oder per Gutschrift erzielt werden können.

Kürzester Code gewinnt.

Testfälle

[] : 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 Zeichen (93 Körper)

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

Es können zwei Zeichen gespeichert werden, wenn der Algorithmus bei Eingabe einer leeren Einkaufsliste abstürzen darf.

GolfScript (54 Zeichen)

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

Dies ist ein Programm, das Eingaben von stdin als durch Leerzeichen getrennte Werte akzeptiert. Sie können ein Zeichen speichern, indem Sie das Eingabeformat als GolfScript-Arrays festlegen.

Testfälle online

Der interessanteste Trick ist .2$>$für einen zerstörungsfreien minBediener.

Meine Analyse der Mathematik ist im Wesentlichen dieselbe wie die von Jan und Ray: Wenn man die Werte von Mod 5 betrachtet, spart man nur bei Transaktionen im Wert von 1 oder 2. Die Kreditkartenoption bedeutet, dass wir niemals aufrunden. Ein Artikel, der 5n + 2 Cent kostet, kann also nicht vom Bündeln profitieren. Ein Artikel im Wert von 5 n + 1 Cent kann auch nicht verkauft werden (da die Kombination von zwei Einsparungen von 1 Cent zu einer Einsparung von 2 Cent keinen Nutzen bringt). 0 ist die additive Identität, daher handelt es sich bei den einzig interessanten Fällen um Werte von 3 und 4. 3+3 = 1und 3+4 = 4+4+4 = 2; wenn wir gemischte 3s und 4s haben dann optimieren wir lieber 3+4über 3+3(streng besser) oder 4+4+4(äquivalent).

C ++: 126 Zeichen

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;}

Willkommen, um eine Anleitung zu geben, damit dieses Programm kürzer wird. Hier ist das Testprogramm, kompilieren Sie mit dem Compiler tdm-gcc 4.7.1 und führen Sie es normal aus.

#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 (wo Pist ein Alias ​​für den obigen Code)

> 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

Bearbeiten : Fälle von {3, 3} und {4,4,4} werden jetzt dank Peter Taylor und cardboard_box bearbeitet.

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]]

Hinweis: Nichtkäufe (Testfall Nr. 1) werden als eingegeben f[{0}].

Wie es funktioniert

1. Für jeden Artikel wird unabhängig von der Zahlungsweise das größte Vielfache von 5 weniger als der jeweilige Preis gezahlt. (Daran führt kein Weg vorbei.)
2. Der Rest von Mod[n, 5]wird dann verarbeitet: 1 und 2 werden zu 0. Nullen bleiben unverändert.
3. Jedes Paar {3, 4} -> {5}; danach jedes Paar {3, 3} -> {5}; dann das Dreifache {4,4,4} -> {10}, falls zutreffend.
4. Die restlichen 4, falls vorhanden, bleiben unverändert (mit Kreditkarte bezahlt).
5. Ursprüngliche Vielfache von 5 summierten sich mit Resten, die in den Schritten (2) bis (4) optimiert wurden (oder nicht).

Testen

a12passt für {3,3} an a13passt für {4,4,4} an

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 Zeichen)

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 Zeichen)

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 Zeichen

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

Das Programm ist im Wesentlichen eine direkte Übersetzung von Jan Dvoraks Ruby-Lösung .

      {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

⍬ ist der leere Vektor.

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

Erklärung:

Bei einem Einkauf können Sie maximal 2 Cent sparen. Wenn Sie also eine Kombination haben, mit der Sie 2 Cent sparen können, kaufen Sie sie einfach auf diese Weise und sie ist optimistisch . Wenn Sie beispielsweise xArtikel mit Preis 3 (Mod 5) und yArtikel mit Preis 4 (Mod 5) haben, können Sie eine min(x, y)Anzahl von (3, 4) Paaren erstellen, wodurch Sie 2 min(x, y)Cent sparen . Dann verwenden Sie die restlichen 3, falls vorhanden, um max(0, x-min(x,y)) / 2Cent zu sparen . Dies kann auch mit berechnet werden(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

Bearbeiten

Diese Lösung ist falsch.