332 - Rational Numbers from Repeating Fractions
Moderator: Board moderators
-
- 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!!!
1 0.9
The output will be: 1 / 1 ----------> WRONG ANSWER!!!
-
- Experienced poster
- Posts: 128
- Joined: Fri Nov 15, 2002 7:45 am
- Location: Kyrgyzstan
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
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
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;
}
-
- New poster
- Posts: 2
- Joined: Sat Sep 13, 2003 4:05 pm
- Location: Bangladesh
332-Why RTE
I got RTE for the following code:
What is the wrong with this 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);
}
}
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
Riyad
i tried to solve the prob as per as the statement of the prob .
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
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.
But they're probably insufficient as my program has not been accepted.
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]
[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]
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![:wink:](./images/smilies/icon_wink.gif)
[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
![:wink:](./images/smilies/icon_wink.gif)
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]
[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]