147  Dollars
Moderator: Board moderators
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]
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]
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[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[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]
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[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.

 Learning poster
 Posts: 55
 Joined: Sat Jan 24, 2004 9:30 pm
 Location: Chittagong
 Contact:
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)
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)

 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[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[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!"
"Finally I have freed myself from the clutches of the garbage fairy!"

 Learning poster
 Posts: 53
 Joined: Sat May 01, 2004 9:31 pm
 Contact:
Wow, autocomplete 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 that much of a diff...
_(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!"

 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[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; 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!