332 - Rational Numbers from Repeating Fractions

Moderator: Board moderators

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

332 Mathematical or algorithmic weakpoint ???

Try this input:
1 0.9

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

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
No, that is correct. We always assume 0.9999999... to be equal to 1.

Bye.
Andrey.

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw

332 - precision problem

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
Rafał Sokołowski

kfree
New poster
Posts: 2
Joined: Wed Aug 06, 2003 9:00 am

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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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
New poster
Posts: 2
Joined: Sat Sep 13, 2003 4:05 pm

332-Why RTE

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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
why don't you post it in volume 3 ?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
The above, and be careful of input like:
1 0.0

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

332 , WA

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

test data for 332

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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
[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
New poster
Posts: 8
Joined: Sat Oct 04, 2003 9:28 am

help! 332 RTE

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
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am
k + j <= 9 so the integer will work

if you use double you may suffer precision problem

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

332 WA

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]