10306 - e-Coins

All about problems in Volume 103. 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
mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

10306 - e-Coins

Post by mido » Fri Sep 20, 2002 10:14 pm

Any problems with this(other than it got WA):
[cpp]
#include <iostream.h>
#include <math.h>
#include <stdio.h>

struct coin
{
int con;
int it;
};

coin arr[50];
long num,m,x,y,e,i,index;
double temp,min;

void play(long x,long y,long index,long count)
{
if (index>m)
return;
temp=sqrt(x*x+y*y);
if (temp>0 && e/temp-floor(e/temp)==0 && (min==0 || (e/temp)*count<min))
{
min=(e/temp)*count;
return;
}
play(x,y,index+1,count);
play(x+arr[index].con,y+arr[index].it,index+1,count+1);
}


void main()
{
cin>>num;
while (num>0)
{
num--;
min=0;
cin>>m>>e;
for (i=0;i<m;i++)
{
cin>>arr.con>>arr.it;
}
play(0,0,index,0);
if (min!=0)
printf("%.0lf\n",min);
else
printf("not possible\n");
}
}
[/cpp]

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

Post by Mahbub » Wed Nov 06, 2002 8:56 am

It may sound srtange to many but this problem has a faster(!) solution than DP , in BFS!!

Here is my code :>> U can perform I/O check with it..

Code: Select all


#define MAX 301
#define QMAX 20000
#define EMAX 41

struct Point
{
	int x;
	int y;
};


int main()
{ 
	int c,case_no,i,s,m,head,tail,found;
	Point e[EMAX];
	
/*	freopen("c:\\10306.txt","r",stdin);  */
	
	scanf("%d",&case_no);

	for(c=0; c<case_no; c++)
	{
		int visited[MAX][MAX] = {{0}};
		int d[MAX][MAX]  ={{0}};
		Point q[QMAX] = {0,0}, u, v;

		scanf("%d%d",&m,&s);

		for(i=0; i<m; i++)
			scanf("%d%d",&e[i].x,&e[i].y);

		head = tail = 0;
		q[0].x = 0;
		q[0].y = 0;
		d[0][0] = 0;
		visited[0][0] = 1;
		tail++;

		found = 0;

		while(head!=tail && !found)
		{
			u = q[head];

			for(i=0; i<m; i++)
			{
				v.x = u.x + e[i].x;
				v.y = u.y + e[i].y;

				if(v.x <= s && v.y <= s)
					if(visited[v.x][v.y] == 0)
					{
						visited[v.x][v.y] = 1;
						d[v.x][v.y] = d[u.x][u.y] + 1;
						if(v.x*v.x + v.y*v.y == s*s)
						{
							found =1;
							printf("%d\n",d[v.x][v.y]);
							break;
						}
						q[tail] = v;
						tail = (tail + 1) % QMAX;
					}
			}

			head = (head+1) % QMAX;
			visited[u.x][u.y] = 1;
		}
		
		if(!found)
		{
			printf("not possible\n"); 
		}
	}
	return 0;
}

jaywinyeah
New poster
Posts: 19
Joined: Sun Aug 17, 2003 10:40 pm

Post by jaywinyeah » Wed Sep 08, 2004 11:35 pm

I have been testing my program, which uses dynamic programming, with the program above. My program is much slower but I get the same answers for hundreds of randomly generated input tests. Time is not the problem, since I have been getting Wrong Answer. Can somebody post some possibly tricky inputs.
LL Cool Jay
The Formula Wizard
Jason Winokur

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Location: Dhaka, Bangladesh
Contact:

Post by popel » Tue May 24, 2005 8:06 pm

My Dynamic solution solves it in abt 0.06 seconds. is the bfs solution faster ?
My code is recursive (and a bit dirty also, there are places for optimization) ---> the iterative solution may include extra solutions in the space --- thus requiring more time. So using static incrementalization with a good pruning method might be faster asymptotically ..... but I am not that comfortable with these techniques so far :(
μδ. ταηνιπ αλ αμιη

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Feb 28, 2006 11:00 pm

recursive dp is often faster than iterative dp in these type of coin problems

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10306 - e-Coins

Post by Jehad Uddin » Tue Nov 10, 2009 5:00 pm

getting WA in this prob, pls help with some I/Os,

Code: Select all

code removed,..
silly mistake ,got acc...
getting frustrated with this forum, no one is replying, :oops: :oops:

ytlau9
New poster
Posts: 6
Joined: Sun May 09, 2010 4:37 pm

10306 - e-coin

Post by ytlau9 » Sun Jul 04, 2010 1:13 pm

can someone gives out tricky test cases?? :roll: :roll:
i hv been tried for a hundred times and still get WA without knowing the reason... :oops:

deebee
New poster
Posts: 2
Joined: Fri Apr 20, 2012 5:17 am

Re: 10306 - e-coin

Post by deebee » Fri Apr 20, 2012 5:21 am

Here are few test cases for anybody still looking for some

Code: Select all

9 

2 5 
0 2 
2 0

3 20 
0 2 
2 0 
2 1

3 5 
3 0 
0 4 
5 5

3 5
3 0
0 4
1 1

4 13
0 1
0 5
0 2
0 3

4 11
1 0
2 0
3 0
10 0

10 13
1 0
2 2
2 0
3 3
6 12
3 11
7 13
14 14
0 5
0 4

2 300
3 0
300 1

40 300
1 0
2 2
2 0
3 3
6 12
3 11
7 13
14 14
0 5
0 4
1 0
2 2
2 0
3 3
6 12
3 11
7 13
14 14
0 5
0 4
1 0
2 2
2 0
3 3
6 12
3 11
7 13
14 14
0 5
0 4
1 0
2 2
2 0
3 3
6 12
3 11
7 13
14 14
0 5
0 4
my accepted code gives

Code: Select all

not possible
10
2
2
3
2
3
100
18

acar_go
New poster
Posts: 8
Joined: Tue Mar 11, 2014 7:33 pm

Re: 10306 - e-Coins

Post by acar_go » Tue Sep 02, 2014 1:19 am

Can someone explain this a bit?

I have figured out this formula x ² + y² = z²

Of test cases can not understand this:

3 20
0 2
2 0
2 1

Following this formula have

4
4
5

s = s ² therefore 20² = 400

According to the statement the result is 10, but according to this approach should be 80.

Help please

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10306 - e-Coins

Post by brianfry713 » Wed Sep 03, 2014 7:56 pm

Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 103 (10300-10399)”