332 - Rational Numbers from Repeating Fractions

[Joseph Kurniawan]

Try this input:
1 0.9

The output will be: 1 / 1 ----------> WRONG ANSWER!!!

[Andrey Mokhov]

No, that is correct. We always assume 0.9999999... to be equal to 1.

Bye.
Andrey.

[Rav]

could somebody tells my how use better precison in this problese. i got TLE but my prog and algorithm work fine, but somthing w precision. Please help.
Here is my source code C++
[cpp]

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <iostream>
using namespace std;

long int euklid (long int x,long int y)
{
long int g=1,t;
while ((x%2==0) && (y%2==0))
{
x/=2;
y/=2;
g*=2;
}
while (x>0)
{
if (x%2==0)
x/=2;
else if (y%2==0)
y/=2;
else
{
t=abs(x-y)/2;
if (x>=y)
x=t;
else
y=t;
}
}
return g*y;
}

long double pot(int pod,int wyk)
{
int wsk,tmp=pod;
if (wyk==0)
return 1;
for (wsk=2;wsk<=wyk;++wsk)
pod*=tmp;
return (long double)(pod);
}

int main()
{
#ifndef ONLINE_JUDGE
close (0); open ("myprog.in", O_RDONLY);
close (1); open ("myprog.out", O_WRONLY | O_CREAT, 0600);
#endif

long double ulamek,tmp;
long int p,q,podz;
int i,j,wsk,liczba,cas=1;

while (cin >> j >> ulamek)
{
cout << "Case " << cas << ": ";
++cas;
i=0;
tmp=ulamek;
while (tmp-(long double)((int)(tmp+0.0000000001))>=0.0000000001) // problem is there beacuse i get (int)((long double)(30))=29
{
++i;
tmp*=(long double)(10);
}
i-=j;
p=(long int)(pot(10,i+j)*(ulamek+0.00000000001))-(long int)(pot(10,i)*(ulamek+0.00000000001)); //or problem is there;
q=(long int)(pot(10,i+j)-pot(10,i));
podz=euklid(p,q);
p/=podz;
q/=podz;
cout << p << '/' << q << '\n';
}
}
[/cpp]
best regards

[kfree]

Code: Select all

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

int main() {
   double x, y;
   int k, j, i, a, b, c=1;

   scanf("%d %lf", &j, &x);
   while (j != -1) {
      y = x * pow(10, j);
      for (k=0; y != (double)((long)y); y*=10,k++);
      a = (int)(pow(10, k+j)*x) - (int)(pow(10,k)*x);
      b = pow(10, k+j) - pow(10,k);
      for (i=a<b ? a : b; a%i || b%i; i--);
      a/=i; b/=i;
      printf("Case %d: %d/%d\n", c++, a, b);
      scanf("%d %lf", &j, &x);
   }
   return 0;
}

[UFP2161]

You don't need to use floating point arithmetic for this. Integers work and are not subject to such errors (unless you overflow of course) =)

[sajib amin]

I got RTE for the following code:

Code: Select all

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

long gcd(long a,long b)
{
   if(b == 0) return a;
   else return gcd(b,a%b);   
}

main()
{
   long n,m,ln;
   long deno,nume,g,kase=0;
   char a[100],b[100];

   while(scanf("%ld",&m) && m != -1)
   {
      scanf(" 0.%[0-9]",a);  
 
      ln = strlen(a);
      n = ln - m ;     
      strcpy(b,a);
      b[n] = 0;   

      nume = atoi(a) - atoi(b);
      deno = pow(10,ln) - pow(10,n);

      g = gcd(nume,deno);      
      nume /= g;
      deno /= g;
  
      printf("Case %ld: %ld/%ld\n",++kase,nume,deno);

   } 

}

What is the wrong with this code?

[Maarten]

why don't you post it in volume 3 ?

[UFP2161]

The above, and be careful of input like:

1 0.0

[Riyad]

i first submitted my code and got RTE (floating point error) as i did not handled the case j=0 . now that i have handled it , i am getting WA . can some one get me some critical IO for the prob .

i tried to solve the prob as per as the statement of the prob .

Bye
Riyad

[WR]

There's a post from May 14, 2002 with test data by Ivan Golubev.

But they're probably insufficient as my program has not been accepted.

[Subeen]

My code got WA. Please help me to find the bug in my code:-
[c]#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

long gcd(long a, long b)
{
if(!b) return a;
else return gcd(b, a%b);
}

void main()
{
int j, k, len, kase=1;
long num, denom, g;
double x, a, b;
char ara[20];

while(1==scanf("%d", &j) && j!=-1)
{
scanf("%s", ara);
len = strlen(ara);
k = len - j - 2;
x = atof(ara);

a = pow(10, k+j) * x;
a = floor(a + .005);
b = pow(10, k) * x;
b = floor(b + 0.0000000005);

num = a - b;
denom = pow(10, k+j) - pow(10, k);

g = gcd(num, denom);

if(g)
{
num /= g;
denom /= g;
}

printf("Case %d: %ld/%ld\n", kase++, num, denom);
}
}[/c]

[tuyide]

here's my code:
[cpp]
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int main()
{
int a,b,i,d,j,k,m,cases=0,y;
char c,p[100];
while(cin>>j,j!=-1)
{cases++;
cin>>c>>c;
cin>>p;
k=strlen(p);
k-=j;
b=atoi(p);

i=1;
for(m=0;m<j;m++)i*=10;
d=b/i;

i=1;
for(m=0;m<j+k;m++)i*=10;
a=i;
i=1;
for(m=0;m<k;m++)i*=10;
a-=i;
//cout<<b-d<<"/"<<a<<endl;
b=b-d;
k=b;j=a;
c=a;d=b;

while(y=j%k,y)
{
j=k;
k=y;
}


cout<<"Case "<<cases<<": "<<b/k<<"/"<<a/k<<endl;


}
}
[/cpp]

how can it be rte?
can anybody give some example?
thx

[jackie]

k + j <= 9 so the integer will work

if you use double you may suffer precision problem

[Abednego]

Does it handle the case of j = 0 correctly? I still can't get it accepted, but this was one of the things I had to fix so far.

[oulongbin]

i don't know why i always get WA,can somebody help me ?thanks;
[cpp]
#include <iostream.h>
#include <math.h>
#include <cstdio>
#include <cstring>

int cas=1;

int gcd(int a,int b)
{
if (a%b==0)
return b;
else
return gcd(b,a%b);
}

int main()
{
char c[100];
int k,j;
int len;
double x;
double r;
int p,q;
int i;
while(cin>>j&&j!=-1)
{
cin.get();
cin.getline(c,100);
len=strlen(c);
k=len-j-2;
x=0;
r=0;
for(i=2;i<len;i++)
{
x+=int(c-48)*pow(10,-(i-1));
}
if(j!=0)
{
r=x*pow(10,k)-int(x*pow(10,k));
p=int(pow(10,k+j)*x+r-pow(10,k)*x);
q=int(pow(10,k+j))-int(pow(10,k));
cout<<"Case "<<cas++<<": "<<p/gcd(p,q)<<"/"<<q/gcd(p,q)<<endl;
}
else
{
p=int(x*pow(10,k));
q=int(pow(10,k));
cout<<"Case "<<cas++<<": "<<p/gcd(p,q)<<"/"<<q/gcd(p,q)<<endl;
}
}
return 0;
}


[/cpp]