SPOJ Problem Set
812. Bits Trocados
Problema: BIT
As Ilhas Weblands formam um reino independente nos mares do Pacífico. Como é um reino recente, a sociedade é muito influenciada pela informática. A moeda oficial é o Bit; existem notas de B$ 50,00, B$10,00, B$5,00 e B$1,00. Você foi contratado(a) para ajudar na programação dos caixas automáticos de um grande banco das Ilhas Weblands.
Tarefa
Os caixas eletrônicos das Ilhas Weblands operam com todos os tipos de notas disponíveis, mantendo um estoque de cédulas para cada valor (B$ 50,00, B$10,00, B$5,00 e B$1,00). Os clientes do banco utilizam os caixas eletrônicos para efetuar retiradas de um certo número inteiro de Bits.
Sua tarefa é escrever um programa que, dado o valor de Bits desejado pelo cliente, determine o número de cada uma das notas necessário para totalizar esse valor, de modo a minimizar a quantidade de cédulas entregues. Por exemplo, se o cliente deseja retirar B$50,00, basta entregar uma única nota de cinquenta Bits. Se o cliente deseja retirar B$72,00, é necessário entregar uma nota de B$50,00, duas de B$10,00 e duas de B$1,00.
Entrada
A entrada é composta de vários conjuntos de teste. Cada conjunto de teste é composto por uma única linha, que contém um número inteiro positivo V, que indica o valor solicitado pelo cliente. O final da entrada é indicado por V = 0.
Saída
Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde n é numerado a partir de 1. Na segunda linha devem aparecer quatro inteiros I, J, K e L que representam o resultado encontrado pelo seu programa: I indica o número de cédulas de B$50,00, J indica o número de cédulas de B$10,00, K indica o número de cédulas de B$5,00 e L indica o número de cédulas de B$1,00. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.
Exemplo
Entrada: 1 72 0 Saída: Teste 1 0 0 0 1 Teste 2 1 2 0 2
Restrições
0 <= V <= 10000 (V = 0 apenas para indicar o fim da entrada)
dados obtidos do site: http://br.spoj.pl
| Adicionado por: | Wanderley Guimarães |
| Data: | 2006-04-19 |
| Tempo limite: | 1s |
| Tamanho do fonte: | 50000B |
| Linguagem permitida: | Todas |
| Origem: | Olimpiada Brasileira de Informatica 2000 |
o Ulisses me enviou um comentário sobre o problema, ele resolveu em PASCAL.
segue abaixo o codigo dele em PASCAL
Program caixa;uses crt;
Label
fim,saque,sair;
type
vetor=array[0..4] of string;
Elem = integer;
lstord = ^Nodo;
Nodo = record
obj: Elem;
prox: lstord;
end;
var
cinq,dez,cinc,um:integer;
cq,dz,cc,u,b,f:integer;
n,a:real;
L:lstord;
resp:char;
PROCEDURE LINHA;
var
i:integer;
begin
for i:=1 to 80 do write('-');
end;
procedure show(x:Elem; l:lstord);
var
a,z:integer;
p:lstord;
v:vetor;
total,totalg,w:integer;
begin
v[0]:='R$50';v[1]:='R$10';v[2]:='R$05';v[3]:='R$01';v[4]:='';
p:= l;
z:=1;
totalg:=0;
write(z,' saque: ');
while (Pnil) do
begin
a:=0;
total:=0;
while (a<4) and (Pnil) do
begin
write (P^.obj,' de ',v[a],', ');
case a of
0:w:=50;
1:w:=10;
2:w:=5;
3:w:=1;
4:w:=0;
end;
total:=total + P^.obj * w;
p:=p^.prox;
a:=a+1;
end;
if (a=4) then
begin
write(' Total: R$ ', total);
totalg:= totalg + total;
writeln;
linha;
writeln;
end;
z:=z+1;
if (p nil) then
write(z,' saque: ');
end;
writeln;
writeln('Ja foi retirado R$',totalg,',00 do caixa');
linha;
writeln;
end;
function Null(L:lstord):boolean;
begin
Null:= (L=nil);
end;
procedure Ins(var L: lstord; X:Elem);
var N,P:lstord;
begin
new(n);
n^.obj:= x;
if Null(l) then
begin
N^.prox := L;
L := N;
end
else
begin
P:= L;
while (P^.proxnil) do
P:= P^.prox;
N^.prox:= P^.prox;
P^.prox:= N;
end;
end;
procedure umm(var um:integer;var n:real;var u:integer);
begin
if (n >= 1) and (um > 0) then
begin
n:= n-1;
um:= um-1;
u:=u+1;
umm(um,n,u);
end;
end;
procedure cincc(var cinc:integer;var n:real;var cc:integer );
begin
if (n >= 5 ) and (cinc > 0) then
begin
n:= n-5;
cinc:= cinc-1;
cc:=cc +1;
cincc(cinc,n,cc);
end
end;
procedure dezz(var dez:integer;var n:real;var dz:integer);
begin
if (n >= 10 ) and (dez > 0) then
begin
n:= n-10;
dez:= dez-1;
dz:=dz+1;
dezz(dez,n,dz);
end;
end;
procedure cinqq(var cinq:integer;var n:real; var cq:integer);
begin
if (n >= 50) and (cinq > 0) then
begin
n:= n-50;
cinq:= cinq-1;
cq:= cq +1;
cinqq(cinq,n,cq);
end;
end;
Begin
clrscr;
cinq:=70;dez:=70;cinc:=70;um:=70;n:=0;a:=1;
while (a 0) do
begin
saque:
textbackground(blue);
textcolor(white);
clrscr;
cq:=0;dz:=0;cc:=0;u:=0;
writeln;
writeln('Notas Diponiveis:');
writeln;
write(' ');
if(cinq>0) then
write(cinq,' de R$50,00 ');
if (dez > 0)then
write(dez,' de R$10,00 ');
if (cinc > 0) then
write(cinc,' de R$05,00 ');
if (um > 0) then
write(um,' de R$01,00 ');
if (cinq+dez+cinc+um=0) then
write('Saque Indisponivel');
writeln;
linha;
writeln;
writeln;
writeln('Digite o Valor do Saque');
writeln;
writeln(' OU ');
writeln;
writeln('Zero, para mostrar quantas notas tem no caixa');
writeln;
writeln(' OU ');
writeln;
writeln('Menos um, Para sair');
writeln;
readln(a);
if (a=-1) then
goto sair;
if (a=0) then
goto fim;
if (a > 0) and (a 0) then
begin
writeln;
writeln(' Valor Maximo para saque R$1000,00. Digite Um valor Menor')
end
else
begin
writeln;
writeln(' Digite Um valor Maior');
end;
readkey;
end;
f:=1;
while (n > 0) and (f=1) do
begin
if (f=1) then
begin
if (n>0) and (n 0) and (n 0) and (n 0) and (n <= (um*1)) then
umm(um,n,u)
else
f:=0;
end;
end;
if (cq+dz+cc+u 0) and (n <= (um*1)) then
begin
writeln;
writeln(' Saque feito com sucesso ');
readkey;
ins(l,cq);ins(l,dz);ins(l,cc);ins(l,u);
end
else
begin
writeln;
if(a0) then
begin
if (um>0) or (cinc>0) or (dez >0) or (cinq > 0) then
writeln(' Valor indisponivel digite outro valor')
else
writeln(' Saque indisponivel dirija-se a outro caixa');
end;
readkey;
end;
end;
fim:
clrscr;
writeln;
Writeln('Foram usadas essas notas');
writeln;
show(b,L);
writeln;
Writeln('Sobram essas notas no Caixa');
writeln(' ',cinq,' de cinquenta, ',dez,' de Dez, ',cinc,' de Cinco, ',um,' de Um');
linha;
writeln;
readkey;
clrscr;
goto saque;
sair:
end.
Por: elzobrito em 21/02/2008
às 5:23 pm
Eu fiz em C, segue abaixo o meu codigo em C.
#include [stdio.h]
int I=0,J=0,K=0,L=0;
int main()
{
int j=0,n=1,r[9999][4];
while(n<=0 || n < 9999)
{
scanf("%d",&n);
if(n 9999)break;
while(n>0)
{
if(n>49)
{
n=n-50;
I++;
}
else
{
if(n>9)
{
n=n-10;
J++;
}
else
{
if(n>4)
{
n=n-5;
K++;
}
else
{
if(n>=1)
{
n=n-1;
L++;
}
}
}
}
}
r[j][0]=I;r[j][1]=J;r[j][2]=K;r[j][3]=L;
I=K=J=L=0;
j++;
}
n=j;
for(j=0;j<n;j++)
{
printf("Teste %d\n%d %d %d %d\n\n", j+1,r[j][0] ,r[j][1] ,r[j][2] ,r[j][3]);
}
return 0;
}
Por: elzobrito em 21/02/2008
às 5:24 pm
Hum, segue minha solução em Python (poderia ser recursivo, mas fica pra depois:
# coding: utf-8
resto = int(raw_input(”"))
divisores = [50, 10, 5]
while resto != 0:
qtd_notas = []
for divisor in divisores:
notas, resto = resto / divisor, resto % divisor
qtd_notas.append(notas)
qtd_notas.append(resto)
print ” “.join(map(str, qtd_notas))
resto = int(raw_input(”"))
Por: Douglas Soares de Andrade em 13/03/2009
às 2:02 pm