## 10113 - Exchange Rates

Moderator: Board moderators

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm

### 10113 - Exchange Rates

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;
}
``````
Jalal : AIUB SPARKS

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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.

``````
Jalal : AIUB SPARKS

Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars
I got it in O^3 Floid Warshall.
in 0.059 sec...

annisizzler
New poster
Posts: 4
Joined: Sat Apr 21, 2012 9:29 am

### Re: 10113 - Exchange Rates

i am getting wa in this problem 10113,plz help.

Code: Select all

``````AC
``````
Last edited by annisizzler on Mon Apr 23, 2012 12:09 am, edited 5 times in total.

rambo1980
New poster
Posts: 15
Joined: Sun Mar 18, 2012 2:45 pm

### Re: 10113 - Exchange Rates

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.

annisizzler
New poster
Posts: 4
Joined: Sat Apr 21, 2012 9:29 am

### Re: 10113 - Exchange Rates

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.