## 275 - Expanding Fractions

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 275 - Expanding Fractions

Why does this code get WA?
[c]
#include<stdio.h>
#define YES 1
#define NO 0
int gcd(int,int);
void main(void)
{
int x,y,found,z,ans,digit[1200],temp[1200],a,b;
while(1)
{
scanf("%d %d",&a,&b);
if(a==0 && b==0)
break;
x=gcd(a,b);
a/=x,b/=x;
a=a%b;
if(a==0)
{
printf(".\nThis expansion terminates.\n\n");
continue;
}
else
{
for(x=0,found=NO;x<1200;x++)
{
a*=10;
digit[x]=a/b;
temp[x]=a%b;
if(a%b==0)
break;
for(y=0;y<x;y++)
if(temp[y]==temp[x])
{
found=YES;
break;
}
if(found)
break;
a=a%b;
}
}
printf(".");
if(!found)
{
for(y=0,z=2;y<=x;y++,z++)
{
printf("%d",digit[y]);
if(z%50==0)
printf("\n");
}
if(z%50!=0)
printf("\n");
printf("This expansion terminates.\n\n");
}
else
{
if(y==0 && digit[x]==digit[y])
x--,ans=x-y+1;
else
ans=x-y;
for(a=0,z=2;a<=x;a++,z++)
{
printf("%d",digit[a]);
if(z%50==0)
printf("\n");
}
if(z%50!=0)
printf("\n");
printf("The last %d digits repeat forever.\n\n",ans);
}
}
}
int gcd(int a,int b)
{
int r;
while(1)
{
r=a%b;
if(r==0)
return b;
if(r==1)
return 1;
a=b,b=r;
}
}
[/c]

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

you can try this
1 397

my output is
.0025188916876574307304785894206549118387909319899
24433249370277078085642317380352644836272040302267
The last 99 digits repeat forever.

.0025188916876574307304785894206549118387909319899
24433249370277078085642317380352644836272040302267

The last 99 digits repeat forever.

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
i got WA too don't know what's wrong
btw, what is the output for 1 1 ?

[pascal]
[/pascal]
Last edited by arc16 on Wed Aug 21, 2002 7:24 pm, edited 1 time in total.

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

### WA

Hi, I find a WA in your program
when the input is
1 300
.00
This expansion terminates.
but my output is
.003
The last 1 digits repeat forever.

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
thanks for reply. I fixed the thing you mention, but still WA
some question:
1. what is the output for:

Code: Select all

``````input:
1 1
0 1
``````
2. should i print blank line in the last case or not?
thank you

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan
Input:
1 1
0 1
my output is
.
This expansion terminates.

.
This expansion terminates.

and my program output a blank line after last input

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
yesterday, i found the official solution of this problem on the net (ACM EC94). And... the output is VERY strange. Take a look at this:

Code: Select all

``````300 31
.``````

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
You miss something in the description. It is stated, that the nominator is always less than the denominator, so there are no such cases you mentioned. That your program got WA must be because it is not correct. Look at the acceptance rate and you will see that the solution is most probably correct, and I don't think that a lot of people send the official solution, because it is cheating.

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
yes, i found my bug already, sometime when the last repeated digit is zero, my program mention the number as terminated
btw, i try to send the off solution not to cheat, but because i didn't know that such case is not exist, and i'm really confused why i got WA on this problem. When i saw that strange output, i guess thats where i go wrong, so i just like to check it out
thank you

21743NX
New poster
Posts: 9
Joined: Tue Aug 27, 2002 8:39 am

### Help with W.A.

For those who are on this problem!!!

bear in mind that the dec places that you should sought in the first place should be 2000.

only then can you compare first 1000 dec with the next.......

Yxy
New poster
Posts: 2
Joined: Thu Jan 16, 2003 9:01 pm
Can someone tell me what is wrong with this?
I'm getting WA's no matter what I do.
Are there any weird input value pairs that I'm missing?
I really can't figure it out...
I even had my program run through all pair combinations of numerators and denominators from 1 to 1000 (took way too long), no luck.
Is it the output format? I'm really stumped....

[java]
import java.io.*;
import java.util.*;

class QRPair {
int quotient;
int remainder;

public QRPair(int q, int r) {
quotient = q;
remainder = r;
}
}

class Main {

static String ReadLn(int maxLg) { // utility function to read from stdin

byte lin[] = new byte[maxLg]; // maxLg == max number of chars in line
int lg = 0; // lg == number of chars read into lin[]
int car = -1;
String line = "";

try {
while (lg < maxLg) {
if ((car < 0) || (car == '\n')) break;
lin[lg++] += car;
}
}
catch (IOException e) {
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin,0,lg));
}

private static int gcd(int n, int d) {
if(d == 0) return n;
return gcd(d,n % d);
}

private static int search(QRPair [] x, QRPair q, int to) {
for(int i = 1; i <= to; i++) {
if(x.quotient == q.quotient && x.remainder == q.remainder) return i;
}
return -1;
}

public static void main(String [] args) {
Main myWork = new Main();
myWork.Begin();
}

void Begin() {

String input;
StringTokenizer idata;
int n = 1, d;

while ((input = Main.ReadLn(255)) != null) {

idata = new StringTokenizer(input);
n = Integer.parseInt(idata.nextToken());
d = Integer.parseInt(idata.nextToken());

if(n == 0 && d == 0) return;

int temp = gcd(n,d);
n /= temp;
d /= temp;
int ARRAY_MAX = d+1;

int i,j,r=0;
QRPair [] arr = new QRPair[ARRAY_MAX];
arr[0] = new QRPair(n/d,n%d);

for(i=0; i<ARRAY_MAX; i++) {
int q = arr.remainder * 10;
QRPair qrp = new QRPair(q/d,q%d);

r = search(arr,qrp,i);

if(r == -1)
arr[i+1] = qrp;
else break;
}

System.out.print("\n.");

for(j=1; j<ARRAY_MAX; j++) {

if(arr[j].quotient == 0 && j == i) {
System.out.println("\nThis expansion terminates.");
break;
}

System.out.print(arr[j].quotient);

if(j == 49 || ( (j > 50) && (j != i) && ((j - 49) % 50 == 0)))
System.out.println();

if(j == i) {
System.out.println("\nThe last " + (i-r+1) + " digits repeat forever.");
break;
}
}
}
}
}
[/java]

Yxy
New poster
Posts: 2
Joined: Thu Jan 16, 2003 9:01 pm
Bah, 5 more WAs and one google search later, I finally found the input causing the problem.
Sheer stupidity, as usual
One line near the bottom needs another boolean test, as pasted below
Oh well....one more down, 1000+ to go =P

[java]
if(arr[j].quotient == 0 && arr[j].remainder == 0 && j == i) {
System.out.println("\nThis expansion terminates.\n");
break;
}
[/java]

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### P 275-Expanding Fraction - Need Special Test Case

need special test case.

Here is my code:

cut..

Thanks.
Red Scorpion :
Last edited by Red Scorpion on Mon May 12, 2003 4:36 am, edited 1 time in total.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
I have fixed my code, but still got WA.
Need Special Test case.
cut...
Last edited by Red Scorpion on Tue May 13, 2003 4:29 am, edited 1 time in total.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
To Arc16 :

You say that you can find your bug,
"Sometime when the last repeated digit is zero, my program mentioned the number as terminated."

Can you explain this more clearly....
I have the same problem with you, and I have try this Problem for a month, butt still I got WA. Please give me a lot of special test cases.

Thanks,
Red Scorpion