## 10306 - e-Coins

Moderator: Board moderators

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

### 10306 - e-Coins

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
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()
{
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);

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

found = 0;

{

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;
}
}

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
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
Contact:
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
Contact:
recursive dp is often faster than iterative dp in these type of coin problems

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

### Re: 10306 - e-Coins

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
New poster
Posts: 6
Joined: Sun May 09, 2010 4:37 pm

### 10306 - e-coin

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

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

### Re: 10306 - e-coin

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

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.