*Your program can get ac by using bignum also.*
**Moderator:** Board moderators

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]

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]

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]

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

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

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]

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

- alu_mathics
- Learning poster
**Posts:**55**Joined:**Sat Jan 24, 2004 9:30 pm**Location:**Chittagong-
**Contact:**

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)

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)

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

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]

[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

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!"

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

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

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

_-(GPI)-_

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

"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

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!

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

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!