147 - Dollars

[anupam]

Your program can get ac by using bignum also.

[Bug!]

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]

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]

check your floating point implementation.. the rest of the code should be fine.

[PMNOX]

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[0][0] = 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];
//r <- answer
printf("%6.2f %17ld\n",x,r);
}
}
[/cpp]

[junbin]

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[0][0] = 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];
//r <- answer
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.

Try reading input as long double instead.

[PMNOX]

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]

convert ur unsigned long data 2 long long(%lld).
use double instead of float.
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.

[Malcolm]

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]

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]

actually never mind...sorry.

[GreenPenInc]

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[10][3000];
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]

[UFP2161]

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]

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...

[Tomislav Novak]

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[0] = 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!