275  Expanding Fractions
Moderator: Board moderators
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=xy+1;
else
ans=xy;
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]
[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=xy+1;
else
ans=xy;
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]
wrong answer
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.
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.
thanks for reply. I fixed the thing you mention, but still WA
some question:
1. what is the output for:
2. should i print blank line in the last case or not?
thank you
some question:
1. what is the output for:
Code: Select all
input:
1 1
0 1
thank you
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.
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
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
Help with W.A.
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!!!
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!!!
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 " + (ir+1) + " digits repeat forever.");
break;
}
}
}
}
}
[/java]
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 " + (ir+1) + " digits repeat forever.");
break;
}
}
}
}
}
[/java]
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]
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]

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
P 275Expanding Fraction  Need Special Test Case
Please help me I always got WA.
need special test case.
Here is my code:
cut..
Thanks.
Red Scorpion :
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.

 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...
Need Special Test case.
cut...
Last edited by Red Scorpion on Tue May 13, 2003 4:29 am, edited 1 time in total.

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