275 - Expanding Fractions

[htl]

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

you can try this
1 397

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

but your output is
.0025188916876574307304785894206549118387909319899
24433249370277078085642317380352644836272040302267

The last 99 digits repeat forever.

[arc16]

i got WA too don't know what's wrong
btw, what is the output for 1 1 ?

[pascal]
[/pascal]

[T.T.]

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

[arc16]

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

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]

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
.

[Adrian Kuegel]

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]

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]

I solved my problem already.

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

I made this mistakes, so made sure you don't!!!

[Yxy]

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) {
car = System.in.read();
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]

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]

Please help me I always got WA.
need special test case.

Here is my code:

cut..

Thanks.
Red Scorpion :

[Red Scorpion]

I have fixed my code, but still got WA.
Need Special Test case.
cut...

[Red Scorpion]

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