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
s.reduce(:+)
(zwykle nawet nie potrzebujesz nawiasów, ale w twoim przypadku ...) i wstawićm
dodatkowe 2 znaki.a,b,c,d=(1..4).map{|i|s.count{|x|x%5==i}}
.0,
zreduce
połączenia, kod zostanie przerwany dla pustych danych wejściowych. Wspomniałem o tym w odpowiedzi. Inlining m wydaje się nie pomagać. Dzięki za ostatnią sugestię - to było dla mnie głupie.(c-m=c>d ?d:c)
co daje dwa znaki.-
ma wyższy priorytet niż=
. Czy przypisanie ma wysoki priorytet po lewej stronie (jak w celu zapewnienia, że lewy operand jest wartością)?GolfScript (54 znaki)
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$>$
dlamin
operatora 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 = 1
oraz3+4 = 4+4+4 = 2
; jeśli mamy mieszane 3s i 4s następnie zoptymalizować przez preferowanie3+4
przez3+3
(ściśle lepiej) lub4+4+4
(odpowiednik).źródło
~):m
) niestety bez zmniejszenia liczby znaków.C ++: 126 znaków
Witaj, udzielamy wskazówek, jak skrócić ten program. Oto program testowy, skompiluj z kompilatorem tdm-gcc 4.7.1 i uruchom go normalnie.
źródło
R 143
Testy (gdzie
P
jest alias dla powyższego kodu)źródło
Mathematica
112 126 167157Edycja : Sprawy {3, 3} i {4,4,4} są teraz obsługiwane dzięki Peterowi Taylorowi i kartonowi_pak.
Uwaga: Non-zakupy (przypadek testowy nr 1) są wprowadzane jako
f[{0}]
.Jak to działa
Mod[n, 5]
jest następnie przetwarzana: 1 i 2 stają się 0. Zera pozostają bez zmian.Testowanie
a12
dostosowuje dla {3,3}a13
dostosowuje dla {4,4,4}źródło
Python 3 (115 znaków)
Python 2 (106 znaków)
źródło
[3,4,9]
powinien dać14
, ponieważ możesz połączyć 3 i 4 centy, aby uzyskać 7 centów, które płacisz gotówką za 5 centów, a pozostałe 9 centów, które płacisz kredytem, ponieważ w przeciwnym razie zaokrągliby w górę.1, 2, 3, 4, 5, 6, 7, 8, 9, 10
, daje to0.0, 0.0, 2.5, 3.33, 5.0, 5.0, 5.0, 7.5, 8.33, 10.0
, co stanowi sumę46.66
. Jednak poprawna odpowiedź jest45
, więc suma liczb, które drukujesz, nie jest poprawną odpowiedzią, a zatem to rozwiązanie jest nieprawidłowe.APL, 58 znaków
Program jest zasadniczo bezpośrednim tłumaczeniem rozwiązania Ruby Jana Dvoraka .
⍬
jest pustym wektorem.źródło
Julia 83C
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 maszx
przedmioty z ceną 3 (mod 5) iy
przedmioty 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ć cimax(0, x-min(x,y)) / 2
centy. Można to również obliczyć za pomocą(max(x,y)-y)/2
Edytować
To rozwiązanie jest złe.
źródło
4 4 4 3 3
czym4 4 4
to połączenie, które może uratować 2 centy, ale kupując go w ten sposób nie jest optymalny. (W rzeczywistości wydaje się, że w ogóle nie bierzesz4 4 4
pod uwagę. Czy ten kod nie zawiedzie ostatniego przypadku testowego?)