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

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

332 Mathematical or algorithmic weakpoint ???

Post by Joseph Kurniawan » Fri Apr 11, 2003 4:36 pm

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

Post by Andrey Mokhov » Sat Apr 12, 2003 6:08 am

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ław

332 - precision problem

Post by Rav » Mon Aug 11, 2003 12:56 pm

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

Post by kfree » Wed Aug 13, 2003 9:31 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;
}

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Thu Aug 21, 2003 6:30 am

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
Location: Bangladesh

332-Why RTE

Post by sajib amin » Sun Oct 05, 2003 6:26 am

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

Post by Maarten » Sun Oct 05, 2003 10:31 am

why don't you post it in volume 3 ?

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sun Oct 05, 2003 5:07 pm

The above, and be careful of input like:
1 0.0

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

332 , WA

Post by Riyad » Wed Feb 18, 2004 8:17 pm

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
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

Post by WR » Tue Mar 09, 2004 1:49 pm

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
Location: Bangladesh
Contact:

Post by Subeen » Wed Mar 17, 2004 2:22 pm

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
New poster
Posts: 8
Joined: Sat Oct 04, 2003 9:28 am

help! 332 RTE

Post by tuyide » Thu Jul 01, 2004 6:41 pm

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:

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Tue Aug 03, 2004 4:59 am

k + j <= 9 so the integer will work

if you use double you may suffer precision problem

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Wed Aug 18, 2004 9:33 am

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

Post by oulongbin » Fri Oct 01, 2004 9:13 am

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]

Post Reply

Return to “Volume 3 (300-399)”