Posted:

**Sat Dec 29, 2001 9:57 am**Is there an algorithm for this problem other than recursively searching all the possibilities? Can anyone give me an answer? Thanks.

Page **1** of **16**

Posted: **Sat Dec 29, 2001 9:57 am**

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

Posted: **Sat Feb 09, 2002 8:22 pm**

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

// @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

if(j + units

}

}

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

Posted: **Sun Feb 10, 2002 11:56 pm**

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

Posted: **Fri Feb 15, 2002 3:11 am**

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

Posted: **Wed Feb 27, 2002 5:16 pm**

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>

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>

Posted: **Thu Feb 28, 2002 2:57 pm**

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.

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.

Posted: **Fri Mar 01, 2002 1:21 am**

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

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

Stefan

Posted: **Fri Mar 01, 2002 9:36 am**

Hi!

Thank's...

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

Thanks a lot

Thank's...

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

Thanks a lot

Posted: **Sun Mar 03, 2002 4:03 pm**

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

Posted: **Mon Mar 04, 2002 10:11 pm**

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

Posted: **Tue Mar 05, 2002 3:28 am**

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.

Posted: **Tue Mar 05, 2002 3:58 am**

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

Posted: **Sat Jul 13, 2002 6:46 am**

[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]

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

if j=a

begin

s:=0;

for k:=1 to i do s:=s+ans[j-a

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]

Posted: **Sun Jul 14, 2002 12:36 pm**

Posted: **Sat Jul 20, 2002 9:35 pm**

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 )

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 )