Economize dinheiro com arredondamentos de preços

18

No Canadá, o centavo não é mais distribuído. Os pagamentos em dinheiro são arredondados para os 5 centavos mais próximos.

O dinheiro pode ser economizado dividindo-se as compras. Por exemplo, dois itens de US $ 1,02 custam US $ 2,04, que arredondam para US $ 2,05, mas ao comprar os itens em compras separadas, cada preço é arredondado para US $ 1,00, totalizando US $ 2,00. No entanto, ao comprar dois itens por US $ 1,03 cada, é melhor comprá-los em uma única compra.

Outra maneira de economizar dinheiro é usar um cartão de crédito quando o arredondamento é desfavorável, porque os pagamentos não são arredondados. Se quisermos dois itens de US $ 1,04, o preço total será de US $ 2,10, independentemente de como dividimos as compras. Portanto, devemos pagar por esses itens com cartão de crédito.

Escreva uma função ou programa que aceite uma lista de preços de itens como números inteiros em centavos e produz o menor preço total possível (em centavos) para os itens que podem ser alcançados através de uma sequência de compras, cada uma em dinheiro ou por crédito.

O menor código vence.

Casos de teste

[] : 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
caixa de papelão
fonte

Respostas:

5

Ruby, 119 105 caracteres (93 corpo)

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

Dois caracteres podem ser salvos se o algoritmo travar ao alimentar uma lista de compras vazia.

John Dvorak
fonte
Você pode mudar para s.reduce(:+)(normalmente você nem precisa de parênteses, mas no seu caso ...) e inline mpor 2 caracteres adicionais.
307 Howard
E claro a,b,c,d=(1..4).map{|i|s.count{|x|x%5==i}}.
307 Howard
@Como remover 0,da reducechamada, o código quebra para a entrada vazia. Eu mencionei isso na resposta. Inlining m parece não ajudar. Obrigado pela última sugestão - isso foi estúpido da minha parte.
John Dvorak
1
Você pode escrever o (c-m=c>d ?d:c)que lhe dá dois caracteres.
307 Howard
@ Howard pensei que iria quebrar porque -tem maior prioridade do que =. Será que a atribuição tem uma alta prioridade no lado esquerdo (como em para garantir que o operando esquerdo seja um valor l)?
John Dvorak
5

GolfScript (54 caracteres)

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

Este é um programa que recebe a entrada do stdin como valores separados por espaço. Um caractere pode ser salvo forçando o formato de entrada a ser como matrizes GolfScript.

Casos de teste online

O truque mais interessante é .2$>$para um minoperador não destrutivo .


Minha análise da matemática é essencialmente a mesma de Jan e Ray: considerando os valores mod 5, a única economia é em transações no valor de 1 ou 2. A opção do cartão de crédito significa que nunca arredondamos. Portanto, um item que custa 5n + 2 centavos não pode se beneficiar do pacote; nem um item vale 5n + 1 centavos (porque combinar duas economias de 1 centavo em uma economia de 2 centavos não traz nenhum benefício). 0 é a identidade aditiva, portanto, os únicos casos interessantes envolvem valores de 3 e 4. 3+3 = 1e 3+4 = 4+4+4 = 2; se tivermos misturado 3s e 4s, otimizaremos preferindo 3+4sobre 3+3(estritamente melhor) ou 4+4+4(equivalente).

Peter Taylor
fonte
+1 - embora esses espaços pareçam tão generosos ;-) Você pode removê-los salvando -m ( ~):m), infelizmente, sem redução na contagem de caracteres.
Howard
@ Howard, eu sei, eu tentei também. : D
Peter Taylor
3

C ++: caractere 126

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

Bem-vindo a dar orientações para colocar esse programa mais curto. Aqui está o programa de teste, compile com o compilador tdm-gcc 4.7.1 e execute normalmente.

#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;
}
jie
fonte
1

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

Testes (onde Pexiste um alias para o código acima)

> 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
flodel
fonte
1

Mathematica 112 126 167 157

Edit : Casos de {3, 3} e {4,4,4} agora são tratados graças a Peter Taylor e paper_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]]

Nota: As não compras (caso de teste nº 1) são inseridas como f[{0}].

Como funciona

  1. Para cada item, o maior múltiplo de 5 menor que o respectivo preço será pago independentemente da forma de pagamento. (Não há como contornar isso.)
  2. O restante de Mod[n, 5]é processado: 1 e 2 se tornam 0. Zeros permanecem inalterados.
  3. Cada par {3, 4} -> {5}; depois cada par {3, 3} -> {5}; então o triplo, {4,4,4} -> {10}, se aplicável.
  4. Os 4 restantes, se houver, permanecem inalterados (pagos com cartão de crédito).
  5. Múltiplos originais de 5 somados com os restantes que foram ajustados (ou não) nas etapas (2) a (4).

Teste

a12ajusta para {3,3} a13ajusta para {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}

DavidC
fonte
1
E quanto a {3,3}?
Peter Taylor
@PeterTaylor. Bom ponto. Ele passou.
DavidC
E quanto a {4,4,4}? Eu acho que com {3,4} -> {5}, {3,3} -> {5} e {4,4,4} -> {10} (nessa ordem), ele deve fornecer respostas ótimas.
cardboard_box
@cardboard_box Você está certo! Veja atualização.
DavidC
Adicionei seus casos de teste adicionais à pergunta. Os que eu tinha foram gerados aleatoriamente para que os casos de canto não aparecessem.
cardboard_box
1

Python 3 (115 caracteres)

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

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
AMK
fonte
2
A pergunta pede o preço total, portanto deve haver uma saída para toda a lista. Por exemplo, a entrada [3,4,9]deve fornecer 14, porque você pode combinar os itens de 3 e 4 centavos para obter uma compra de 7 centavos que você paga em dinheiro com 5 centavos de dólar e o item de 9 centavos restantes que você paga com crédito, pois, caso contrário, eles seriam arredondados.
cardboard_box
2
Dado 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, isso dá 0.0, 0.0, 2.5, 3.33, 5.0, 5.0, 5.0, 7.5, 8.33, 10.0, o que equivale a 46.66. No entanto, a resposta correta é 45, portanto, a soma dos números impressos não é a resposta correta e, portanto, esta solução está incorreta.
Nolen Royalty
Essa resposta foi wroted quando o trabalho não contém "total" ainda
AMK
2
Receio ter de recomendar a exclusão. Asker não mudou os requisitos - ele os esclareceu. Se o preço de cada item separadamente foi desejado, por que a menção de uma "sequência de compras / compra única" e a discussão de qual é favorável?
precisa
Eu apago respostas erradas. Agora é mais curtas respostas Python
AMK
0

APL, 58 caracteres

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

O programa é essencialmente uma tradução direta da solução 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

é o vetor vazio.

Volatilidade
fonte
0

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

Explicação:

Em uma compra, você pode economizar 2 centavos no máximo. Portanto, se você tem uma combinação que pode economizar 2 centavos, basta comprar dessa maneira e será otimista . Por exemplo, se você possui xitens com preço 3 (mod 5) e yitens com preço 4 (mod 5), pode criar um min(x, y)número de (3, 4) pares, o que economiza 2 min(x, y)centavos. Então você usa os 3 restantes, se houver, para economizarmax(0, x-min(x,y)) / 2 centavos. Isso também pode ser calculado por(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

Editar

Esta solução está errada.

Raio
fonte
+1 para usar uma linguagem relativamente desconhecido que pode ser interessante para aprender
John Dvorak
É uma nova linguagem em desenvolvimento ativo. Combina muitas forças de diferentes idiomas. Espero que mais pessoas possam saber disso.
Ray
A análise não é muito completa, porque se você tem 4 4 4 3 3, então 4 4 4é uma combinação que pode salvar 2 centavos, mas comprá-lo dessa maneira não é o ideal. (Na verdade, você não parecem estar a tomar 4 4 4em consideração em tudo Não este código falhar o último caso de teste.?)
Peter Taylor