275 - Expanding Fractions

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

275 - Expanding Fractions

Post by htl » Sun Jul 21, 2002 1:35 pm

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

wrong answer

Post by T.T. » Mon Aug 12, 2002 8:31 am

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

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Sat Aug 17, 2002 4:44 am

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

Post by T.T. » Sun Aug 18, 2002 10:39 am

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

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Sun Aug 18, 2002 11:30 am

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

Post by T.T. » Mon Aug 19, 2002 5:17 am

Input:
1 1
0 1
my output is
.
This expansion terminates.

.
This expansion terminates.

and my program output a blank line after last input :wink:

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Wed Aug 21, 2002 7:31 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Aug 21, 2002 11:19 pm

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

Post by arc16 » Thu Aug 22, 2002 4:25 am

yes, i found my bug already, sometime when the last repeated digit is zero, my program mention the number as terminated :wink:
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.

Post by 21743NX » Wed Oct 30, 2002 6:59 am

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
New poster
Posts: 2
Joined: Thu Jan 16, 2003 9:01 pm

Post by Yxy » Thu Jan 16, 2003 9:06 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) {
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
New poster
Posts: 2
Joined: Thu Jan 16, 2003 9:01 pm

Post by Yxy » Thu Jan 16, 2003 9:31 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

Post by Red Scorpion » Tue Jan 28, 2003 8:12 am

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

Here is my code:

cut..

Thanks.
Red Scorpion : :x
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

Post by Red Scorpion » Fri Jan 31, 2003 5:43 am

I have fixed my code, but still got WA.
Need Special Test case.
cut...
:oops:
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

Post by Red Scorpion » Fri Jan 31, 2003 6: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 :wink:

Post Reply

Return to “Volume 2 (200-299)”