332 - Rational Numbers from Repeating Fractions

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

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 332 why RTE please help me

Post by mf » Sun Jan 18, 2009 4:45 am

double c = a*x; // c = 507462687
Here's the first error. x is not equal to the mathematical constant 0.507462687, because double can't represent it.
x represents the value 0.507462687 +/- eps, where eps is some value of the order of about 1e-15 (double's precision). And as a result of that, when you multiply x by 1e10, you don't get the exact integer 507462687. Instead you get c = 507462687 +/- eps2, where eps2 is now about 0.00001.

Same thing for variable d - it's the integer you want it to be, plus or minus an epsilon of about 0.00001.

Next, the following statement:
long long num = (long long) (c-d);
tells the computer to find the difference between c and d, round it down to the lower integer, and store it in variable num. But because c and d are not integers, c-d most likely also will not be an integer. It could end up being something like 418.999999, which after cast to long long will become 418, and not 419 as you might have hoped.

I hope this sheds some light on this mystery with rounding. Here are a couple of pages for further reading, if you're interested - [1], [2].

toru
New poster
Posts: 17
Joined: Tue Dec 30, 2008 10:38 am

Re: 332 - Rational Numbers from Repeating Fractions

Post by toru » Wed Mar 18, 2009 6:32 am

Hi !!, Can anyone plzzzz show me how to get 11/20 for the input " 0 0.55 ". as here i m getting 0 for both the upper value and lower value...... then how can i proceed??????? I m not getting it..................Thanks in advance.

megh_putra016

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 332 - Rational Numbers from Repeating Fractions

Post by Jehad Uddin » Sat May 23, 2009 1:51 am

hello everyone i m getting frustrated with this prob,can any one tell me whats the wrong with this code

Code: Select all

long long int gcd(long long int a,long long int b)
{
	if(a<b) swap(a,b);
	return ((b==0)?a:gcd(b,a%b));
}

long long int power(long long int a,long long int b)
{
 long long int i=1,ans=1;
 for(i=1;i<=b;i++)
	 ans*=a;
 return  ans;
}

long double count(char *str)
{
 long long int i=0,l;
 long double a=0;
 l=strlen(str);
 for(i=2;i<l;i++)
 {
  a+=(str[i]-48)*pow(10,1-i);
 }
 return a;
}
int main()
{
 char str[15];
 long double a,p,q,r;
 long long int j,k,x,y,z,m,n=0;
 while(cin>>j)
 {
  if(j==-1) break;
  cin>>str;
  n++;
  k=strlen(str)-2;
  k=k-j;
  a=count(str);
  if(j==0) 
  {
   z=a*power(10,k);
   m=power(10,k);
  }
  else 
  {
  x=power(10,k+j);
  y=power(10,k);
  p=double(x)*a;
  r=double(y)*a;
  q=power(10,k+j)-power(10,k);
  z=(long long int)p-(long long int)r;
  m=(long long int)(q);
  }
  x=gcd(z,m); 
  z=z/x;
  m=m/x;
 cout<<"Case "<<n<<": "<<z<<"/"<<m<<endl;
  }
 return 0;
}

meghla
New poster
Posts: 3
Joined: Sat Dec 26, 2009 4:29 pm

Re: 332 why RTE please help me

Post by meghla » Sun Feb 21, 2010 4:08 pm

after 9 RTE i,ve got accetped;
i think ,when the input is 3 0.0000 then calculating GCD code terminates;
so it causes RTE..................................

Bella Swan
New poster
Posts: 6
Joined: Mon Jun 21, 2010 9:21 pm

Re: 332 - Rational Numbers from Repeating Fractions

Post by Bella Swan » Wed Mar 30, 2011 6:01 pm

View solution here which does not contain any floating point process

http://acmsolutionuva119.blogspot.com/2 ... ating.html

Yousuf
New poster
Posts: 13
Joined: Thu Jun 09, 2011 8:22 am

332 getting wrong answer Help please.

Post by Yousuf » Fri Jul 08, 2011 10:24 pm

removed

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 332 - Rational Numbers from Repeating Fractions

Post by plamplam » Sun Aug 28, 2011 8:44 pm

I really like this problem(May be because I got AC in first try :P). You can solve this very simply. I'll explain with an example.
Consider the input 2 0.318.

Here, j = 2, and k = 1. You can approximate X to be 0.318 and use it in the formula but there is a better way. Take the double number as string(You can always convert it to double from string easily with atof). As j = 2, so the digits 18 will be repeated after 0.318. Now use strcat to add the repeating digits(here 18) to the original string 5-6 times and there you go. An approximation for x :wink:. Now use atof to convert the string to a double value and just apply the formula. Just be careful about cases where j can be 0. And also try to make your own power function as advised by Jan. To convert from double to int just use the round function in cpp to avoid precision error. (e.g 5 calculated as 4.999999987 and a statement like int = double value may result in a precision error. Instead use int value = round(double value)).
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 332 - Rational Numbers from Repeating Fractions

Post by Mukit Chowdhury » Fri Jan 10, 2014 12:51 pm

No need of double/floating type ... :)

coder.tanvir
New poster
Posts: 11
Joined: Mon Mar 09, 2015 10:30 am

Re: 332 - Rational Numbers from Repeating Fractions

Post by coder.tanvir » Sun Mar 22, 2015 4:48 pm

i think working with double for this problem is so risky.

Post Reply

Return to “Volume 3 (300-399)”