## 147 - Dollars

Moderator: Board moderators

limelight_team
New poster
Posts: 3
Joined: Sat Dec 29, 2001 2:00 am
Is there an algorithm for this problem other than recursively searching all the possibilities? Can anyone give me an answer? Thanks.

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Yes, dynamic programming, but someone help me. This ain't workin'! Why not?!?

// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID: 17243NT 147 C++ "Dynamic Programming" */

// Send to judge@uva.es

#include <iostream.h>
#include <iomanip.h>

const int MAX = 5000;

int am[MAX + 1];
int units[11] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

int main() {
double amount;
int i, j;

am[0] = 1;
for(i = 0; i < 11; i++) {
for(j = 0; j <= MAX - units; j++) {
if(j + units <= MAX) am[j + units] += am[j];
}
}

while(cin >> amount)
cout << setiosflags(ios::fixed) << setw(5) << setprecision(2)
<< amount << setw(12) << am[(int) (amount * 100)] << endl;

return 0;
}

// @END_OF_SOURCE_CODE

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
I should really read more carefully. I didn't take into consideration that 0.00 ends the reading.

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Well, it still doesn't work. Anybody got ideas why not?

Lawrence
New poster
Posts: 17
Joined: Sat Feb 09, 2002 2:00 am
Location: China
Contact:
I don't know, I can't understand your code to calculate the table (though I just did this problem today!), should j increment only 1?

But I must point out that using (int) (amount * 100) is a dangerous thing, I have had times when the value was stored as 54.999987 while it should be 55, and (int) made it to 54
:-<, so I always use something like (int)(amount * 100 + 0.0005) now.

<font size=-1>[ This Message was edited by: Lawrence on 2002-02-27 16:19 ]</font>

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

I have no idea why my program doesn't work. It is quite a simle task, but why it always gets WA. Please help..

Program p147;
CONST
mon:array[1..10] of longint = (5,10,20,50,100,200,500,1000,2000,5000);
VAR
tab:array[0..10001] of longint;
po:real;
x,y,z:longint;

begin
tab[0]:=1;
for y:=1 to 10 do
begin
x:=0;
while x<=5000 do
begin
tab[x+mon[y]]:=tab[x+mon[y]]+tab[x];
x:=x+1;
end;

end;

repeat
if po<>0 then
begin
x:=trunc(po*100);
Writeln(po:5:2,tab[x]:12);
end;
until po=0;
end.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Maybe you have the same problem as the other guy just some days ago. Did you read that discussion? Try if this helps:

x:=trunc(po*100+0.5);

Stefan

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

Thank's...

I have no idea why it works but it works...

Thanks a lot

Lawrence
New poster
Posts: 17
Joined: Sat Feb 09, 2002 2:00 am
Location: China
Contact:
Hi, just look back at the previous thread of this problem, I have explained this phenomena a little there.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
This is just a classic rounding algorithm. (double*10^number of digits to round+0.5)/10^number of digits to round.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
The problem is that double or float can't exactly represent things like 1/10 or 1/100. They *always* round in these cases. Sometimes up, sometimes down. So if you don't want to rely on your luck, you should be careful.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
It is always good to compare to epsilon rather than 0. Instead of (X==0), do (X<0.0001).

nayaya
New poster
Posts: 9
Joined: Sat Jun 08, 2002 1:57 pm

### 147 Why WA?

[pascal]
program p147(input,output);
type
aaa=array[1..1000,1..10] of longint;
sss=array[1..10] of integer;
var
r:real;
ans:aaa;
a:sss;
i,n,k,j:integer;
m:longint;

procedure findans;
var
s:longint;
begin
a[1]:=1;a[2]:=2;a[3]:=4;a[4]:=10;a[5]:=20;a[6]:=40;a[7]:=100;
a[8]:=200;a[9]:=400;a[10]:=1000;
for i:=1 to 10 do
for j:=1 to 1000 do
if j<a then ans[j,i]:=0 else
if j=a then ans[j,i]:=1 else
begin
s:=0;
for k:=1 to i do s:=s+ans[j-a,k];
ans[j,i]:=s;
end;
end;

procedure work;
begin
findans;
while r>=0.01 do
begin
m:=0;
n:=trunc(r*100) div 5;
for i:=1 to 10 do m:=m+ans[n,i];
writeln(r:5:2,m:12);
end;
end;

Begin
work;
end.

[/pascal]

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### problem 147

who can send me the source of this problem...?

e-mail: hankii@ms10.url.com.tw

thanks!

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
sorry. I solved this problem, but I can't send my source code.

Because I know that using other programmer's source code is

very unfair thing. ( Maybe it can't increase for your ability -_- )

Instead, I'll give you some hint for solving this problem.

It use standard dynamic programming. All possible case of making

money is sum of sub-case. ( Think about the rule of dynamic programming.

Making recurrence equation for using dynamic programming. )

In addition, this site have some problem which is simuliar to problem

147.

( e.g. problem 357 )