147 - Dollars

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sat Dec 27, 2003 12:10 pm

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

Post by Bug! » Thu Jan 08, 2004 11:59 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?

Post by Malcolm » Fri Jan 23, 2004 4:45 pm

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

Post by junbin » Sat Jan 24, 2004 5:58 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?

Post by PMNOX » Sat Jan 31, 2004 5:51 pm

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Re: 147 why do i get WA?

Post by junbin » Sun Feb 01, 2004 8:14 am

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.

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

Post by PMNOX » Sun Feb 01, 2004 11:41 am

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);
;)

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

Post by alu_mathics » Sun Feb 01, 2004 8:50 pm

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. :wink:
cuii e

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

Post by Malcolm » Tue Feb 03, 2004 2:38 pm

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?

Post by cfalcon » Sun Apr 18, 2004 1:16 pm

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

Post by cfalcon » Sun Apr 18, 2004 1:22 pm

actually never mind...sorry.

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

TLE - General Question

Post by GreenPenInc » Mon May 03, 2004 1:26 am

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]
_-(GPI)-_

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

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Mon May 03, 2004 1:55 am

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.

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

Post by GreenPenInc » Mon May 03, 2004 2:43 am

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

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

147 (Dollars) - WA

Post by Tomislav Novak » Thu Jun 03, 2004 4:53 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! ;)

Post Reply

Return to “Volume 1 (100-199)”