Page 1 of 1
10306 - e-Coins
Posted: Fri Sep 20, 2002 10:14 pm
by 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]
Posted: Wed Nov 06, 2002 8:56 am
by 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;
}
Posted: Wed Sep 08, 2004 11:35 pm
by 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.
Posted: Tue May 24, 2005 8:06 pm
by 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
Posted: Tue Feb 28, 2006 11:00 pm
by sclo
recursive dp is often faster than iterative dp in these type of coin problems
Re: 10306 - e-Coins
Posted: Tue Nov 10, 2009 5:00 pm
by 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,
10306 - e-coin
Posted: Sun Jul 04, 2010 1:13 pm
by ytlau9
can someone gives out tricky test cases??
i hv been tried for a hundred times and still get WA without knowing the reason...
Re: 10306 - e-coin
Posted: Fri Apr 20, 2012 5:21 am
by 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
Re: 10306 - e-Coins
Posted: Tue Sep 02, 2014 1:19 am
by 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
Re: 10306 - e-Coins
Posted: Wed Sep 03, 2014 7:56 pm
by brianfry713