Page 1 of 6

674 - Coin Change

Posted: Thu Dec 12, 2002 2:58 pm
by anupam

:oops:
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?
please help..

Code: Select all

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

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

void writeball(int &x) 
{ 
     cout<<ball.x<<" "<<ball.y<<" "<<ball.direction<<" "<<ball.lifetime<<" "<<x<<endl; 
} 


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; 
        cin>>ball.x>>ball.y>>ball.direction>>ball.lifetime; 
        //ball.x++; 
        //ball.y++; 
        int orgx,orgy; 
        while(ball.lifetime > 1) 
        { 
              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--; 
                ball.lifetime -= A[ball.x][ball.y].cost; 
                //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 
             ball.lifetime--; 
        } 

        cout<<partialscore<<endl; 
        totalscore+=partialscore; 
    } 
    cout<<totalscore<<endl; 
   #ifndef ONLINE_JUDGE 
       int www; 
       cin>>www; 
   #endif 
} [/cpp]
[/i][/b]

Posted: Thu Dec 12, 2002 3:04 pm
by anupam
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]

Posted: Thu Dec 12, 2002 5:00 pm
by Dominik Michniewski
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

Posted: Sat Dec 14, 2002 7:07 am
by anupam
will u please describe the way of dp to solve it?
i have little knowledge about it.
thnx. :( :(

Posted: Mon Dec 16, 2002 9:36 am
by Dominik Michniewski
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 :D )

Regards
Dominik

Posted: Wed Dec 18, 2002 10:43 am
by anupam
:oops: [/b]

Posted: Wed Dec 18, 2002 10:48 am
by anupam
thanks dominik.[/b]

674

Posted: Tue Mar 18, 2003 6:20 am
by yahoo
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.


Posted: Tue Mar 18, 2003 3:45 pm
by Hisoka
you can count all answer from 1 to 7489 before you begin your input proses. :wink: and with this you not necessary allways count 1 to n after your input. 8)

Posted: Thu Mar 20, 2003 4:45 pm
by yahoo
Thanks hisoka for your reply. I have made a so silly mistake. i got accepted now :P :P :P Thank again.

674

Posted: Sat Jun 14, 2003 2:40 am
by bugzpodder
in problem 674, I am the only one who's run time is exactly 0.00.674! :D

Posted: Sat Jun 14, 2003 3:15 am
by Dmytro Chernysh
Cool!!!

But Junyi Cheng has time 0:00.666 :-)

Posted: Mon Dec 01, 2003 5:30 pm
by Alexei Rybalkin
Please, somebody, give me some inputs/outputs for this problem.

Should I use LongInteger in this problem? :-?

Thanks.

Posted: Tue Dec 02, 2003 12:35 am
by Per
31 bits are enough.

For input

Code: Select all

0
3141
7489
The output is

Code: Select all

1
68808096
2146113925

Posted: Tue Dec 02, 2003 1:11 am
by Farid Ahmadov
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!