## 147 - Dollars

Moderator: Board moderators

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Your program can get ac by using bignum also.
"Everything should be made simple, but not always simpler"

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am
To anybody whose got WA for this problem, I used to get WA for this problem because of 2 reason:
1. Output format
2. Use rounding from double to int conversion
n=(int)(input*100+0.5)
Hope this will help all of You.
Regard,
Andre

Malcolm
New poster
Posts: 5
Joined: Fri Jan 23, 2004 4:34 pm
Location: Taiwan

### 147 Can anyone help?

I used the same code and solved 357 and 674, but I got WA in 147.
Did miss something?? frustrated....
(I searched for post of 147 but I can't get the problem in my program)

[c]
#include <stdio.h>
#define MAX 6000

long long ways[ MAX + 1 ] = { 0 };
int coins[ 11 ] = { 2000, 1000, 400, 200, 100, 40, 20, 10, 4, 2, 1 };

int main( void ) {
int i, j, n = 6000, m, c;
float x;

m = 11;
ways[ 0 ] = 1;
for( i = 0; i < m; i++ ) {
c = coins[ i ];
for( j = c; j <= MAX; j++ )
ways[ j ] += ways[ j - c ];
}

while( 1 ) {
scanf( "%f", &x );

if( x == 0.0 )
break;

n = (int)( x * 20.0 + 0.5 );

printf( "%6.2f%ll17d\n", x, ways[ n ] );
}
}
[/c]

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
check your floating point implementation.. the rest of the code should be fine.

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

### 147 why do i get WA?

I can't figure it out why i am getting WA
maybe it is IO problem?

[cpp]
#include <stdio.h>
#define MAXV 8000
#define NCOINS 11

int main( void ) {
int i, j, k;
int coins[] = { 1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000 };
unsigned long d[MAXV+1][NCOINS];
for(i = 0; i <= MAXV; ++i)
for(j = 0; j < NCOINS; ++j)
d[j] = 0;
d = 1;
for(i = 0; i <= MAXV; ++i)
for(j = 0; j < NCOINS; ++j)
if(i - coins[j] >= 0)
for(k = 0; k <= j; ++k)
d[j] += d[i - coins[j]][k];

while( 1 ) {
float x;
scanf( "%f", &x );
float input_number = x;
int value = (int)(input_number*20+0.4);
if( value <= 0)
break;
unsigned long r;
for(i = 0, r = 0; i < NCOINS; ++i)
r += d[value];
printf("%6.2f %17ld\n",x,r);
}
}
[/cpp]

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

### Re: 147 why do i get WA?

PMNOX wrote:I can't figure it out why i am getting WA
maybe it is IO problem?

[cpp]
#include <stdio.h>
#define MAXV 8000
#define NCOINS 11

int main( void ) {
int i, j, k;
int coins[] = { 1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000 };
unsigned long d[MAXV+1][NCOINS];
for(i = 0; i <= MAXV; ++i)
for(j = 0; j < NCOINS; ++j)
d[j] = 0;
d = 1;
for(i = 0; i <= MAXV; ++i)
for(j = 0; j < NCOINS; ++j)
if(i - coins[j] >= 0)
for(k = 0; k <= j; ++k)
d[j] += d[i - coins[j]][k];

while( 1 ) {
float x;
scanf( "%f", &x );
float input_number = x;
int value = (int)(input_number*20+0.4);
if( value <= 0)
break;
unsigned long r;
for(i = 0, r = 0; i < NCOINS; ++i)
r += d[value];
printf("%6.2f %17ld\n",x,r);
}
}
[/cpp]

I think it's either a floating point error or a input error.. I haven't really gone through your code, but I assumed you are using DP to solve it.. so unless there's a typo, I doubt it's wrong algorithmically.

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
i have rewritten this algorithm to remove floating points and i got WA.
Then i found that in last lint there is bug
printf("%6.2f %17ld\n",x,r);
//
it should be printf("%6.2f %17lld\n",x,r); alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
convert ur unsigned long data 2 long long(%lld).
And finally change
int value = (int)(input_number*20+0.4);
to
int value = (int)(input_number*20+0.5);//silly but works
u will get ur code P.E. cuii e

Malcolm
New poster
Posts: 5
Joined: Fri Jan 23, 2004 4:34 pm
Location: Taiwan
Finallly, I got accepted. I changed flaot to double and changed the last line to
[c]
printf( "%6.2lf%17lld\n", x, ways[ n ] );
[/c]

cfalcon
New poster
Posts: 13
Joined: Fri Dec 19, 2003 12:33 pm

### p147 - have they changed the question?

hi,
i had some range problems with this so i checked some earlier posts and it turned out that all answers fit within longint and that the denominations are different from some sample codes posted. but i noticed the output for some inputs are same for both denominations. so has the question changed? thanx a lot.

the denominations i see in the question are the following
5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 (in cents)
but the ones in the sample posts are the following
2000, 1000, 400, 200, 100, 40, 20, 10, 4, 2, 1 (in cents)

cfalcon
New poster
Posts: 13
Joined: Fri Dec 19, 2003 12:33 pm
actually never mind...sorry.

GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

### TLE - General Question

I seem to be getting TLEs a lot for programs I submit, when I have no idea why. The program will run just fine on my machine, usually under a split second, and it'll get stuck on valladolid for reasons I can't fathom. Here's one quick example (it's for #147):

[cpp]
1 #include <iostream>
2 #include <stdio.h>
3
4 using namespace std;
5
6 int value[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};
7 unsigned long m;
8
9 void init()
10 {
11 for (int i = 0; i < 10; i++)
12 {
13 for (int j = 0; j < 3000; j++)
14 {
15 m[j] = 0;
16 }
17 }
18 }
19
20 int get_array_value(int amt, int highest)
21 {
22 return m[highest - 1][amt / 10 - 1];
23 }
24
25 void set_array_value(int amt, int highest, int val)
26 {
27 m[highest - 1][amt / 10 - 1] = val;
28 }
29
30 unsigned long combo_count(int amt, int highest)
31 {
32 unsigned long count = 0;
33 if (amt <= 5) return 1;
34 if (highest == 0) return 1;
35 if (get_array_value(amt, highest) > 0) return get_array_value(amt, highest);
36 int money = amt;
37 while (money >= 0)
38 {
39 count += combo_count(money, highest - 1);
40 money -= value[highest];
41 }
42 set_array_value(amt, highest, count);
43 return count;
44 }
45
46 int main()
47 {
48 init();
49 double amt;
50 int howmuch;
51 while (true)
52 {
53 cin >> amt;
54 if (amt == 0.0) break;
55 amt += 0.001;
56 howmuch = (int)(amt * 100);
57 printf("%6.2f%17u\n", amt, combo_count(howmuch, 10));
58 }
59 return 0;
60 }
[/cpp]

On my machine it gives results instantly, even for 300.00 (the maximum). But I get TLE when I submit. Anyone know why?[/cpp][/code]
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Try testing it on an input file with all the possible input values. Your program took approximately 30 seconds to run on my computer for that amount of data.

GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:
Wow, auto-complete sucks. Makes me look like (more of a) dumbass. Anyway, I fixed the problems. First, I was passing an int to the array instead of an unsigned long; fixing that gave me WA. Then I changed the output format from u to lld and all was well. Still not sure why it's so fast on my computer and so slow seemingly everywhere else. I have a P4 something, but I wouldn't expect it to make that much of a diff...
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

### 147 (Dollars) - WA

Hello!

I keep getting wrong answer (although I'm using proper double to int conversion, (int)(i * 100 + 0.5)) with the following code:

[c]
#include <stdio.h>

#define MAXAMOUNT 30000
#define NUMNOTES 11

int notes[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 100000};
long long ways[MAXAMOUNT + 1];

void calculate()
{
int i, j;

memset(ways, 0, sizeof(ways));
ways = 1;

for (i = 0; i < NUMNOTES; i++)
for (j = notes; j <= MAXAMOUNT; j++)
ways[j] += ways[j - notes];
}

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

calculate();

while (scanf("%lf", &amount) == 1)
{
if (amount == 0) break;
cents = (int)(amount * 100 + 0.5);

printf("%6.2lf%17lld\n", amount, ways[cents]);
}

return 0;
}
[/c]

Thanks in advance! 