10367 - Equations

All about problems in Volume 103. 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
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

10367 - Equations

Post by Jan » Sat Sep 08, 2007 4:06 am

Well, I m getting RTE in the new judge. But couldnt figure out why. Can anyone help? Sorry for posting such a long code.

Code: Select all

/*
	Author       :	Jan
	Problem Name :	Equations
	Algorithm    :	Math
	Complexity   :
*/

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#define min(a,b) ((a) < (b) ? (a) : (b))
#define max(a,b) ((a) > (b) ? (a) : (b))

#define CLR(a) memset(a,0,sizeof(a))

/* A Class with a/b format */

class fraction
{
public:
	int a,b;
	fraction()
	{
		a=0;
		b=1;
	}
	fraction(int x)
	{
		a=x;
		b=1;
	}
	fraction(int x,int y)
	{
		a=x;
		b=y;
		(*this).normalize();
	}
	void normalize();
	fraction operator + (fraction);
	fraction operator - (fraction);
	fraction operator * (fraction);
	fraction operator / (fraction);

	bool operator == (fraction);
	bool operator > (fraction);
	bool operator < (fraction);
	bool operator != (fraction);
};

int compare(fraction a,fraction b)
{
	return a.a*b.b-a.b*b.a;
}

int gcd(int a,int b)
{
	return (!b) ? a : gcd(b,a%b);
}

int lcm(int a,int b)
{
	int d;

	if(a<0) a=-a;
	if(b<0) b=-b;
	d=gcd(a,b);
	d=a/d*b;
	return d;
}

void fraction::normalize()
{
	int d;
	
	if(b==0)
		b=1;
	if(a==0)
	{
		b=1;
		return;
	}
	if(b<0)
	{
		a*=-1;
		b*=-1;
	}
	d=gcd(abs(a),abs(b));
	a/=d;
	b/=d;
}

fraction fraction::operator + (fraction X)
{
	fraction Z;

	Z.b=lcm(b,X.b);
	Z.a=(Z.b/b)*a+(Z.b/X.b)*X.a;
	Z.normalize();
	return Z;
}

fraction fraction::operator - (fraction X)
{
	fraction Z;

	Z.b=lcm(b,X.b);
	Z.a=(Z.b/b)*a-(Z.b/X.b)*X.a;
	Z.normalize();
	return Z;
}

fraction fraction::operator * (fraction X)
{
	fraction Z;

	Z.a=a*X.a;
	Z.b=b*X.b;
	Z.normalize();
	return Z;
}

fraction fraction::operator / (fraction X)
{
	fraction Z;

	Z.a=a*X.b;
	Z.b=b*X.a;
	Z.normalize();
	return Z;
}

bool fraction::operator == (fraction X)
{
	return compare((*this),X)==0;
}

bool fraction::operator > (fraction X)
{
	return compare((*this),X)>0;
}

bool fraction::operator < (fraction X)
{
	return compare((*this),X)<0;
}

bool fraction::operator != (fraction X)
{
	return compare((*this),X)!=0;
}

int cases,caseno;
char a[100000];

struct info
{
	int a,b,c;	// ax + by + c = 0
}A,B;

info check()
{
	int sum;
	int i,sign,flag,gotequal,k;
	char *p,b[1000];
	info A;

	A.a=A.b=A.c=0;
	p=strtok(a," ");
	sign=gotequal=1;
	while(p)
	{
		sscanf(p,"%s",b);
		p=strtok(NULL," ");
		if(b[0]=='=')
		{
			gotequal=-1;
			sign=-1;
			continue;
		}
		k=1;
		if(b[0]=='+')
		{
			if(!b[1])
			{
				sign=1*gotequal;
				continue;
			}
			i=1;
		}
		else if(b[0]=='-')
		{
			if(!b[1])
			{
				sign=-1*gotequal;
				continue;
			}
			i=1;
			k=-1;
		}
		else
			i=0;
		sum=flag=0;
		for(;b[i];i++)
		{
			if(b[i]=='x')
			{
				flag=1;
				break;
			}
			if(b[i]=='y')
			{
				flag=2;
				break;
			}
			sum=sum*10+b[i]-48;
		}
		if(flag && !sum)
			sum=1;
		sum=sum*sign*k;
		if(!flag)
			A.c+=sum;
		else if(flag==1)
			A.a+=sum;
		else
			A.b+=sum;
	}
	return A;
}

void input()
{
	gets(a);
	gets(a);
	A=check();
	gets(a);
	B=check();
}

inline void print(fraction k)
{
	if(k.b==1)
		printf("%d\n",k);
	else
		printf("%d/%d\n",k.a,k.b);
}

void process()
{
	if(caseno++)
		puts("");
	if((!A.a && !A.b && A.c) || (!B.a && !B.b && B.c))
	{
		puts("don't know");
		puts("don't know");
		return;
	}
	fraction matrix[3][4],k,l;

	if(!A.a && ( B.a || (!A.b && B.b)) )
	{
		info temp;

		temp=A;
		A=B;
		B=temp;
	}
	matrix[1][1]=A.a;
	matrix[1][2]=A.b;
	matrix[1][3]=(-A.c);

	matrix[2][1]=B.a;
	matrix[2][2]=B.b;
	matrix[2][3]=(-B.c);

	if(matrix[1][1]!=0)
	{
		k=matrix[1][1];
		matrix[1][1]=matrix[1][1]/k;
		matrix[1][2]=matrix[1][2]/k;
		matrix[1][3]=matrix[1][3]/k;

		k=matrix[2][1]/matrix[1][1];
		matrix[2][1]=matrix[2][1]-matrix[1][1]*k;
		matrix[2][2]=matrix[2][2]-matrix[1][2]*k;
		matrix[2][3]=matrix[2][3]-matrix[1][3]*k;

		if(matrix[2][2]==0 && (matrix[2][3]!=0 || matrix[1][2]!=0))
		{
			puts("don't know");
			puts("don't know");
			return;
		}
		if(matrix[2][2]!=0)
		{
			l=matrix[2][3]/matrix[2][2];
			k=matrix[1][3]-l*matrix[1][2];
			print(k);
			print(l);
		}
		else
		{
			print(matrix[1][3]);
			puts("don't know");
		}
	}
	else
	{
		puts("don't know");
		if(matrix[1][2]==0)
		{
			puts("don't know");
			return;
		}
		k=matrix[1][3]/matrix[1][2];
		if(matrix[2][2]!=0)
		{
			l=matrix[2][3]/matrix[2][2];
			if(l!=k)
			{
				puts("don't know");
				return;
			}
		}
		print(k);
	}
}

int main()
{
	scanf("%d",&cases);
	while(cases--)
	{
		input();
		process();
	}
	return 0;
}
Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Re: 10367 - Equations

Post by Dominik Michniewski » Thu Mar 31, 2011 1:09 pm

I have got Wrong Answer with my code, but I can't find mistake :(

Could anyone post me some I/O ?

Maybe I miss some special cases ?
Could anyone help me ... ? :-)


NEVER MIND: I finally got Accepted :-) I forgot about printing empty line between cases :-/
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Post Reply

Return to “Volume 103 (10300-10399)”