Page 1 of 1

### 10113 - Exchange Rates

Posted: Sat Oct 01, 2005 12:26 pm
hi, i m getting wrong answer in 10113 [exchange rates]. please give me some test data if you can. thanks

Code: Select all

``````#include<stdio.h>
#include<string.h>
#define MAX 70
int graph[MAX][MAX];
struct node
{
char name[30];
};
node allnode[MAX];
int c;
int get(char n[])
{
int i;
for(i=0;i<c;i++)
if(strcmp(n,allnode[i].name)==0)
return i;
return -1;
}
int gcd(int x,int y)
{
int temp;
while(y)
{
temp=x;
x=y;
y=temp%y;
}
return x;
}
int mark[MAX];
int dfs(int x,int y,int *p,int *q)
{
int i;
if(x==y)
return 1;
for(i=0;i<c;i++)
if(mark[i]==0 && graph[x][i])
{
mark[i]=1;
*p*=graph[x][i];
*q*=graph[i][x];
int g=gcd(*p,*q);
*p/=g;
*q/=g;
if(dfs(i,y,p,q))
return 1;
}
return 0;
}
int main()
{
char n1[30],n2[30],op[10];
int v1,v2,x,y,p,q;
freopen("10113.in","r",stdin);
memset(graph,0,sizeof(graph));
while(scanf("%s",op)==1)
{
if(strcmp(op,".")==0)
break;
else if(strcmp(op,"!")==0)
{
scanf("%d%s%s%d%s",&v1,n1,op,&v2,n2);
x=get(n1);
if(x==-1)
{
x=c;
strcpy(allnode[c++].name,n1);
}

y=get(n2);
if(y==-1)
{
y=c;
strcpy(allnode[c++].name,n2);
}
graph[x][y]=v1;
graph[y][x]=v2;

}
else
{
scanf("%s%s%s",n1,op,n2);
x=get(n1);
y=get(n2);
if(x<0 || y<0)
printf("? %s = ? %s\n",n1,n2);
else
{
p=q=1;
memset(mark,0,sizeof(mark));
if(dfs(x,y,&p,&q)==0)
printf("? %s = ? %s\n",n1,n2);
else
printf("%d %s = %d %s\n",p,n1,q,n2);
}

}
}
return 0;
}
``````

Posted: Fri Oct 07, 2005 5:24 am
ok, lets talk about the algo i am using........

Code: Select all

``````i make a graph using the exchange relations. then i apply dfs to reach from source to goal. and i calculate the rates.

if
3 pen = 4 pencil

lets say i gave pen a number : 1 and pencil a number: 6

then graph[1][6]=3
and graph[6][1]=4
so when i go from 1 to 6, i use 3:4
and if i go from 6 to 1, i use 4:3
i use gcd to reduce my answer in every term, that it doesn't overflow.

``````

Posted: Wed Jan 24, 2007 11:39 pm
I got it in O^3 Floid Warshall.
in 0.059 sec...

### Re: 10113 - Exchange Rates

Posted: Sat Apr 21, 2012 9:39 am
i am getting wa in this problem 10113,plz help.

Code: Select all

``````AC
``````

### Re: 10113 - Exchange Rates

Posted: Sat Apr 21, 2012 2:07 pm
Anika, at first search the board for existing topics before creating a new thread.
And before pasting your code, click on the "code" button above, or else your code will loose clarity due to omission of the whitespace and tab characters.

### Re: 10113 - Exchange Rates

Posted: Sun Apr 22, 2012 4:31 am
rambo1980 wrote:Anika, at first search the board for existing topics before creating a new thread.
And before pasting your code, click on the "code" button above, or else your code will loose clarity due to omission of the whitespace and tab characters.
i found no other thread for this problem 10113 except this,if there is any other will u plz give the link?and i post my code now as u say.