10113 - Exchange Rates

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

10113 - Exchange Rates

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

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

Post 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.

Jalal : AIUB SPARKS

Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

Post by Tanu »

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

Post by annisizzler »

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

Post 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.

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

Re: 10113 - Exchange Rates

Post 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.

Post Reply

Return to “Volume 101 (10100-10199)”