Page 1 of 1

10113 - Exchange Rates

Posted: Sat Oct 01, 2005 12:26 pm
by CodeMaker
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
by CodeMaker
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
by Tanu
I got it in O^3 Floid Warshall.
in 0.059 sec...

Re: 10113 - Exchange Rates

Posted: Sat Apr 21, 2012 9:39 am
by annisizzler
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
by rambo1980
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
by annisizzler
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.