## 674 - Coin Change

Moderator: Board moderators

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

### 674 - Coin Change

i don't know how to solve it by a short time. i use the formula
(1+x+x^2+...)(1+x^5+x^10+...)(..)..
but it takes long time and i have got tle.
is there any way to solve it in a short time?

Code: Select all

[cpp]
#include <iostream.h>
#define ONLINE_JUDGE
struct pinball
{
bool bouncer;
int value;
int cost;
};

struct {
int x,y;
int direction;
}ball;

void writeball(int &x)
{
}

void main()
{

int col,row,wallcost,nBouncers;
pinball A[53][53];
cin>>col>>row>>wallcost>>nBouncers;
for(int i=1;i<=col;i++)
for(int j=1;j<=row;j++)
{
A[i][j].bouncer = false;
A[i][j].value = 0;
A[i][j].cost = 0;
}
//int minx=1,miny=1;
for(int i=1;i<=col;i++)
{
A[i][1].bouncer = true;
A[i][1].value = 0;
A[i][1].cost = wallcost;
A[i][row].bouncer = true;
A[i][row].value = 0;
A[i][row].cost = wallcost;
}
for(int j=1;j<=row;j++)
{
A[1][j].bouncer = true;
A[1][j].value = 0;
A[1][j].cost = wallcost;
A[col][j].bouncer = true;
A[col][j].value = 0;
A[col][j].cost = wallcost;
}
int bouncercol,bouncerrow,bouncervalue,bouncercost;
for(int i=0;i<nBouncers;i++)
{
cin>>bouncercol>>bouncerrow>>bouncervalue>>bouncercost;
A[bouncercol][bouncerrow].bouncer = true;
A[bouncercol][bouncerrow].value=bouncervalue;
A[bouncercol][bouncerrow].cost=bouncercost;
}
int partialscore;
int totalscore=0;
while(!cin.eof())
{

partialscore=0;
//ball.x++;
//ball.y++;
int orgx,orgy;
{
orgx=ball.x;
orgy=ball.y;
switch (ball.direction)
{
case 0: /* direction right (add col) */
ball.x++;
break;
case 1: /* direction up (add row) */
ball.y++;
break;
case 2: /* direction left (minus col) */
ball.x--;
break;
case 3: /* direction down (minus row) */
ball.y--;
break;
}
#ifndef ONLINE_JUDGE
writeball(partialscore);
#endif
if(A[ball.x][ball.y].bouncer == true)
{
if (ball.direction == 0) /* update new direction */
ball.direction = 3;
else
ball.direction--;
//if(ball.lifetime >1)   //maybe this must be turned on
partialscore += A[ball.x][ball.y].value;
ball.x = orgx;
ball.y = orgy;
}
#ifndef ONLINE_JUDGE
writeball(partialscore);
#endif
}

cout<<partialscore<<endl;
totalscore+=partialscore;
}
cout<<totalscore<<endl;
#ifndef ONLINE_JUDGE
int www;
cin>>www;
#endif
} [/cpp]
[/i][/b]
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
sorry,
that is not the problem.
the code is here?
sorry....

Code: Select all

[cpp]
#include<stdio.h>
#define N 2100
long int n,a[5][N];
double m;
void rec(void)
{
long int i,j,k,l,p,q;
for(i=0;i*50<N;i++)
{
if(a[0][i]>n) break;
for(j=0;j*25<N;j++)
{
if((a[0][i]+a[1][j])>n) break;
for(k=0;k*10<N;k++)
{
if((a[0][i]+a[1][j]+a[2][k])>n) break;
for(l=0;l*5<N;l++)
{
if((a[0][i]+a[1][j]+a[2][k]+a[3][l])>n) break;
for(p=0;p<N;p++)
{
q=a[0][i]+a[1][j]+a[2][k]+a[3][l]+a[4][p];
if(q>n) break;
if(q==n) m++;
}
}
}
}
}
}

main(void)
{
long int i,r;
freopen("c:\\in.txt","w",stdout);
for(i=0;i<N;i++) a[4][i]=i;
for(i=0;i*5<N;i++) a[3][i]=i*5;
for(i=0;i*10<N;i++) a[2][i]=i*10;
for(i=0;i*25<N;i++) a[1][i]=i*25;
for(i=0;i*50<N;i++) a[0][i]=i*50;
n=r=999;
while(1)
{
//r=scanf("%ld",&n);
n++;
if(r==EOF || n==2000) break;
m=0;
rec();
printf("%.0lf\n",m);
fflush(stdout);
}
return 0;
}[/cpp]
"Everything should be made simple, but not always simpler"

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
It's problem for Dynamic Programming ...
My accepted solution takes 0.18 sec and has time-complexity O(N^2)

In my opinion you are count it wrong and not one, but several times

If input looks like
1000
1000
1000
........ hundred times
you must ecpected TLE ....

Dominik

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
will u please describe the way of dp to solve it?
i have little knowledge about it.
thnx.
"Everything should be made simple, but not always simpler"

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
it's very easy .. (This is the one of a few problems , where DP is easy to show ...)

If I correct remember algorithm is following:
1. declare array which have size for all possible input values (there is not so big array - 10000 element or less )
2. It's easy to find formula to find the number of ways , which are necesary to give money for 1,5 cents coin... (for all inputs)
3. So we have only three coins to consider: 10,25,50. Because we know, how to get all numbers less then N, ...
so for given M > N ways[M] = ways[M] + ways[M-10] + ways[M-25] + ways[M-50] (of course - only if M is bigger than 50 ) in other case sum has less factors )

Regards
Dominik

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
[/b]
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
thanks dominik.[/b]
"Everything should be made simple, but not always simpler"

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

### 674

I used dynamic programming in solving this problem. But i got tle. Will anybody see my code and tell where i am wrong. Thanks in advance.
Here is my code:

Code: Select all

Code has bee cut because after some modification it is accepted.


Last edited by yahoo on Thu Mar 20, 2003 4:52 pm, edited 1 time in total.

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
you can count all answer from 1 to 7489 before you begin your input proses. and with this you not necessary allways count 1 to n after your input.

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
Thanks hisoka for your reply. I have made a so silly mistake. i got accepted now Thank again.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

### 674

in problem 674, I am the only one who's run time is exactly 0.00.674!

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
Cool!!!

But Junyi Cheng has time 0:00.666

Alexei Rybalkin
New poster
Posts: 6
Joined: Mon Dec 01, 2003 5:16 pm
Location: Orenburg, Russia
Please, somebody, give me some inputs/outputs for this problem.

Should I use LongInteger in this problem?

Thanks.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
31 bits are enough.

For input

Code: Select all

0
3141
7489
The output is

Code: Select all

1
68808096
2146113925

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
Some IO for you:

INPUT

Code: Select all

0
57
129
134
239
277
300
386
393
455
510
535
568
610
637
642
790
1426
1446
1498
1503
1590
1600
1624
1635
1647
1691
1722
1931
2116
2261
2455
2547
2663
2703
2707
2765
2827
2915
3258
3349
3915
3960
4261
4691
4800
4862
4928
5001
5151
5246
5331
5376
5559
5826
5853
5975
6071
6168
6239
6321
6423
6482
6543
6620
6796
6962
6973
7026
7104
7355
7414
7481
7489
OUTPUT

Code: Select all

1
62
558
628
4160
7098
9590
23124
24216
42230
64064
76384
93418
124124
144144
148421
327216
3131855
3305565
3771460
3820626
4790368
4908497
5151289
5339224
5467319
6072570
6503070
10190440
14574076
18894799
26139150
30107714
35816715
37980910
38258165
41705076
45379809
51340620
79289342
88293002
164338960
171932760
229494139
335794790
368086385
386652189
407548350
432699251
486474872
523030235
557449884
576345348
656770352
792830259
806417782
876993480
933653312
993015250
1038534000
1095890112
1166373065
1210262495
1255379026
1317482439
1461345024
1607484130
1616679680
1667962743
1739848682
2001748100
2061906700
2140421225
2146113925
Good luck!
_____________
NO sigNature