W Kanadzie grosz nie jest już w obiegu. Płatności gotówkowe są zaokrąglane do najbliższych 5 centów.

Pieniądze można zaoszczędzić, dzieląc zakupy. Na przykład dwa przedmioty o wartości 1,02 USD kosztują 2,04 USD, co zaokrągla w górę do 2,05 USD, ale przy zakupie przedmiotów w oddzielnych zakupach każda cena zaokrągla się do 1,00 USD, co daje w sumie 2,00 USD. Jednak kupując dwa przedmioty po 1,03 USD za każdy, lepiej kupić je za jednym razem.

Innym sposobem na zaoszczędzenie pieniędzy jest użycie karty kredytowej, gdy zaokrąglanie jest niekorzystne, ponieważ płatności kredytowe nie są zaokrąglane. Jeśli chcemy dwóch przedmiotów po 1,04 USD, całkowita cena zaokrągli w górę do 2,10 USD, niezależnie od tego, jak podzielimy zakupy. Dlatego powinniśmy płacić za te przedmioty kartą kredytową.

Napisz funkcję lub program, który akceptuje listę cen produktów jako liczby całkowite w centach i generuje najniższą możliwą cenę całkowitą (w centach) dla tych produktów, które można osiągnąć poprzez sekwencję zakupów, każdą gotówką lub kredytem.

Najkrótszy kod wygrywa.

Przypadki testowe

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

Rubinowy, 119 105 znaków (93 ciało)

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

Dwa znaki mogą zostać zapisane, jeśli algorytm może ulec awarii po podaniu pustej listy zakupów.

GolfScript (54 znaki)

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

Jest to program, który pobiera dane wejściowe ze standardowego wejścia jako wartości oddzielone spacjami. Jeden znak można zapisać, zmuszając format wejściowy, aby był jak tablice GolfScript.

Przypadki testowe online

Najciekawsza sztuczka jest .2$>$dla minoperatora nieniszczącego .

Moja analiza matematyki jest zasadniczo taka sama jak Jana i Raya: biorąc pod uwagę wartości mod 5, jedyne oszczędności dotyczą transakcji o wartości 1 lub 2. Opcja karty kredytowej oznacza, że ​​nigdy nie zaokrąglamy w górę. Zatem przedmiot, który kosztuje 5n + 2 centy, nie może skorzystać z połączenia; przedmiot o wartości 5n + 1 centów też nie może (ponieważ połączenie dwóch 1 centów oszczędności w 2 centów oszczędności nie daje żadnych korzyści). 0 to tożsamość addytywna, więc jedynymi interesującymi przypadkami są wartości 3 i 4. 3+3 = 1oraz 3+4 = 4+4+4 = 2; jeśli mamy mieszane 3s i 4s następnie zoptymalizować przez preferowanie 3+4przez 3+3(ściśle lepiej) lub 4+4+4(odpowiednik).

C ++: 126 znaków

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

Witaj, udzielamy wskazówek, jak skrócić ten program. Oto program testowy, skompiluj z kompilatorem tdm-gcc 4.7.1 i uruchom go normalnie.

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

Testy (gdzie Pjest alias dla powyższego kodu)

> 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

Edycja : Sprawy {3, 3} i {4,4,4} są teraz obsługiwane dzięki Peterowi Taylorowi i kartonowi_pak.

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

Uwaga: Non-zakupy (przypadek testowy nr 1) są wprowadzane jako f[{0}].

Jak to działa

1. Za każdy przedmiot zostanie zapłacona największa wielokrotność 5 mniej niż odpowiednia cena, niezależnie od formy płatności. (Nie można tego obejść.)
2. Pozostała część Mod[n, 5]jest następnie przetwarzana: 1 i 2 stają się 0. Zera pozostają bez zmian.
3. Każda para {3, 4} -> {5}; następnie każda para {3, 3} -> {5}; następnie potrójne, {4,4,4} -> {10}, jeśli dotyczy.
4. Pozostałe 4, jeśli istnieją, pozostają niezmienione (płatne kartą kredytową).
5. Oryginalne wielokrotności 5 zsumowane z resztkami, które zostały poprawione (lub nie) w krokach (2) do (4).

Testowanie

a12dostosowuje dla {3,3} a13dostosowuje dla {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 znaków)

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 znaków)

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 znaków

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

Program jest zasadniczo bezpośrednim tłumaczeniem rozwiązania Ruby Jana Dvoraka .

      {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

⍬ jest pustym wektorem.

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

Wyjaśnienie:

Za jednym zakupem możesz zaoszczędzić najwyżej 2 centy. Więc jeśli masz kombinację, która może zaoszczędzić Ci 2 centy, po prostu kup ją w ten sposób, a będzie optymalna . Na przykład, jeśli masz xprzedmioty z ceną 3 (mod 5) i yprzedmioty z ceną 4 (mod 5), możesz utworzyć min(x, y)liczbę (3, 4) par, co pozwoli ci zaoszczędzić 2 min(x, y)centy. Następnie wykorzystujesz pozostałe 3, jeśli takie istnieją, aby zaoszczędzić ci max(0, x-min(x,y)) / 2centy. Można to również obliczyć za pomocą(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

Edytować

To rozwiązanie jest złe.