147  Dollars
Moderator: Board moderators

 New poster
 Posts: 3
 Joined: Sat Dec 29, 2001 2:00 am
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; 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
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 20020227 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 20020227 16:19 ]</font>
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.

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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[ja,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 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[ja,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]

 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 subcase. ( 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 subcase. ( 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 )