10306 - e-Coins

[mido]

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]

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]

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.

[popel]

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]

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

[Jehad Uddin]

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,

[ytlau9]

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

[deebee]

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]

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]

http://www.algorithmist.com/index.php/UVa_10306