OJ Board

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

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.

Code: Select all

AC