147 - Dollars

[limelight_team]

Is there an algorithm for this problem other than recursively searching all the possibilities? Can anyone give me an answer? Thanks.

[paulhryu]

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]

I should really read more carefully. I didn't take into consideration that 0.00 ends the reading.

[paulhryu]

Well, it still doesn't work. Anybody got ideas why not?

[Lawrence]

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]

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
readln(po);
if po<>0 then
begin
x:=trunc(po*100);
Writeln(po:5:2,tab[x]:12);
end;
until po=0;
end.

[Stefan Pochmann]

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]

Hi!

Thank's...

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

Thanks a lot

[Lawrence]

Hi, just look back at the previous thread of this problem, I have explained this phenomena a little there.

[C8H10N4O2]

This is just a classic rounding algorithm. (double*10^number of digits to round+0.5)/10^number of digits to round.

[Stefan Pochmann]

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]

It is always good to compare to epsilon rather than 0. Instead of (X==0), do (X<0.0001).

[nayaya]

[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
read(r);
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);
readln(r);
end;
end;

Begin
work;
end.

[/pascal]

[hank]

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

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



thanks!

[soyoja]

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 )