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

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

### 332 why WA???

pliz give me some inputs and ouputs.

[cpp]
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
long long ten(int n) // calculate the 10^n
{
long long m = 1;
for(int i = 0;i < n;i++)
{
m *= 10;
}
return m;
}
long long gcd(long long a,long long b)
{
while(b > 0)
{
a = a % b;
a ^= b;
b ^= a;
a ^= b;
}
return a;
}
double convert(char string[12]) // convert a string to a double number
{
double n = 0;
double d = 1;
for(int i = 2;string != '\0';i++)
{
d *= 0.1;
n += (d * (string - '0'));
}
return n;
}
void output(char string[12],int j) // j is the number of the repeat digits
{
if(j == 0)
{
double x = convert(string);
long long numerator = (long long)(x * ten(strlen(string) - 2));
long long denominator = (long long)(ten(strlen(string) - 2));
}
else
{
int k = strlen(string) - 2 - j;
double x = convert(string);
long long numerator = (long long)(ten(k + j) * x) - (long long)(ten(k) * x);
//the decimal expansion of the ten(k + j) * x must be equal to that of the ten(k) * x,
//so i forced them to long long
long long denominator = ten(k + j) - ten(k);
}
long long gcdn = gcd(numerator,denominator);
cout << numerator / gcdn << '/' << denominator / gcdn << endl;

}
int main()
{
char string[12];
int dr,n = 1;
while(cin >> dr)
{
if(dr == -1) break;
cout << "Case " << n++ << ": ";
cin >> string;
output(string,dr);
}
return 0;
}
[/cpp]
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
You can find more data posted somewhere (don't remember where exactly).

input:

Code: Select all

``````2 0.318
1 0.3
2 0.09
6 0.714285
6 0.714285000
1 0.9999
9 0.123456789
8 0.987654321
9 0.574454131
5 0.83777471
1 0.22222222
9 0.111111111
9 0.222222222
9 0.333333333
9 0.444444444
9 0.555555555
9 0.666666666
9 0.777777777
9 0.888888888
9 0.999999999
9 0.000000000
1 0.200
8 0.200000000
8 0.020000000
0 0.3
0 0.5
0 0.55
1 0.55
6 0.142857
0 0.9
1 0.9
6 0.076923
0 0.678453453
0 0.1
2 0.31818
9 0.345678993
2 0.25
1 0.3
0 0.3
0 0.0
5 0.99999
6 0.714285
0 0.5
0 0.35
-1
``````
output:

Code: Select all

``````Case 1: 7/22
Case 2: 1/3
Case 3: 1/11
Case 4: 5/7
Case 5: 119047381/166666500
Case 6: 1/1
Case 7: 13717421/111111111
Case 8: 54869684/55555555
Case 9: 574454131/999999999
Case 10: 41888317/49999500
Case 11: 2/9
Case 12: 1/9
Case 13: 2/9
Case 14: 1/3
Case 15: 4/9
Case 16: 5/9
Case 17: 2/3
Case 18: 7/9
Case 19: 8/9
Case 20: 1/1
Case 21: 0/1
Case 22: 1/5
Case 23: 1/5
Case 24: 2000000/99999999
Case 25: 3/10
Case 26: 1/2
Case 27: 11/20
Case 28: 5/9
Case 29: 1/7
Case 30: 9/10
Case 31: 1/1
Case 32: 1/13
Case 33: 678453453/1000000000
Case 34: 1/10
Case 35: 7/22
Case 36: 38408777/111111111
Case 37: 25/99
Case 38: 1/3
Case 39: 3/10
Case 40: 0/1
Case 41: 1/1
Case 42: 5/7
Case 43: 1/2
Case 44: 7/20
``````

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
[cpp]
#include <iostream.h>
int main()
{
double d = 0.987654321;
cout << (long long)(1000000000 * d) << endl;
return 0;
}
[/cpp]

the output would be:

98654320

that's why i always get wrong answer.
but how can i control it?
is there any type that be preciser than double?
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
I've gotten AC,thanks
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

### 332 about RunTime Error~~

Well~I got runtime error for thie questions so many times.
It always tell SIGFPE.But I even don't understand well about this.
Could anybody help me to fix the wrong???
[c]#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(void)
{
int j,a[12]={0},k,ans_a,ans_b,all,i,all_1,co=0;
char ch[0];
scanf("%d",&j);
while(j!=-1)
{
co++;
k=0;ans_a=0;ans_b=1;all=0;all_1=1;
scanf("%c",&ch);
scanf("%c",&ch);
scanf("%c",&ch);
scanf("%c",&ch);
while(ch[0]!=10)
{
k++;
a[k]=atoi(ch);
all=all*10+a[k];
scanf("%c",&ch);
}
k=k-j;
for(i=1;i<=j+k;i++)
{
if(i<=k)
{
ans_a=ans_a*10+a;
ans_b=ans_b*10;
}
all_1=all_1*10;
}
if(j!=0)
{
ans_b=all_1-ans_b;
ans_a=all-ans_a;
}
else
{ans_a=all;}
all=ans_a;
all_1=ans_b;
while(i!=0)
{
i=all_1%all;
all_1=all;
all=i;
}
printf("Case %lu: ",co);
printf("%lu/%lu\n",ans_a/all_1,ans_b/all_1);
scanf("%d",&j);
}
return 0;
}[/c]

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
SIGFPE is caused by divide by zero error probably all_1 is zero from some input
printf("%lu/%lu\n",ans_a/all_1,ans_b/all_1);
if u can think of it .. u can do it in software.

someone1985
New poster
Posts: 2
Joined: Mon Jan 03, 2005 9:00 pm
I got exactly the same as the output of the test cases above but I still get wrong answer for this problem. Anyone can give me some critical test cases for this problem, thanks you!

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Thank you, WR !
Your IO was very useful for me.

Someone1985 ,
I have just one naive question ...

Do you print
Case #<N>
as a beginning of each line.

That was one of the errors I had
Funny, I know.
Last edited by Sedefcho on Thu Apr 07, 2005 6:43 pm, edited 1 time in total.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Last edited by Sedefcho on Thu Apr 07, 2005 6:43 pm, edited 1 time in total.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Here is some sample I/O

INPUT:

Code: Select all

``````2 0.318
1 0.3
2 0.09
6 0.714285
6 0.714285000
1 0.9999
9 0.123456789
8 0.987654321
9 0.574454131
5 0.83777471
1 0.22222222
9 0.111111111
9 0.222222222
9 0.333333333
9 0.444444444
9 0.555555555
9 0.666666666
9 0.777777777
9 0.888888888
9 0.999999999
9 0.000000000
1 0.200
8 0.200000000
8 0.020000000
0 0.3
0 0.5
0 0.55
1 0.55
6 0.142857
0 0.9
1 0.9
6 0.076923
0 0.678453453
0 0.1
2 0.31818
9 0.345678993
2 0.25
1 0.3
0 0.3
0 0.0
5 0.99999
6 0.714285
0 0.5
0 0.35
-1
``````

OUTPUT

Code: Select all

``````Case 1: 7/22
Case 2: 1/3
Case 3: 1/11
Case 4: 5/7
Case 5: 119047381/166666500
Case 6: 1/1
Case 7: 13717421/111111111
Case 8: 54869684/55555555
Case 9: 574454131/999999999
Case 10: 41888317/49999500
Case 11: 2/9
Case 12: 1/9
Case 13: 2/9
Case 14: 1/3
Case 15: 4/9
Case 16: 5/9
Case 17: 2/3
Case 18: 7/9
Case 19: 8/9
Case 20: 1/1
Case 21: 0/1
Case 22: 1/5
Case 23: 1/5
Case 24: 2000000/99999999
Case 25: 3/10
Case 26: 1/2
Case 27: 11/20
Case 28: 5/9
Case 29: 1/7
Case 30: 9/10
Case 31: 1/1
Case 32: 1/13
Case 33: 678453453/1000000000
Case 34: 1/10
Case 35: 7/22
Case 36: 38408777/111111111
Case 37: 25/99
Case 38: 1/3
Case 39: 3/10
Case 40: 0/1
Case 41: 1/1
Case 42: 5/7
Case 43: 1/2
Case 44: 7/20``````
Maybe I have it from some other thread.
I never prepare so large I/O.

someone1985
New poster
Posts: 2
Joined: Mon Jan 03, 2005 9:00 pm
Of course yes, but now still got wrong answer haha

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Someone1985,
send me your code if you like,
maybe I can help you
because I have this problem ACC already.

Just email me your code.

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
WR wrote:You can find more data posted somewhere (don't remember where exactly).

input:

Code: Select all

``````2 0.318
1 0.3
2 0.09
6 0.714285
6 0.714285000
1 0.9999
9 0.123456789
8 0.987654321
9 0.574454131
5 0.83777471
1 0.22222222
9 0.111111111
9 0.222222222
9 0.333333333
9 0.444444444
9 0.555555555
9 0.666666666
9 0.777777777
9 0.888888888
9 0.999999999
9 0.000000000
1 0.200
8 0.200000000
8 0.020000000
0 0.3
0 0.5
0 0.55
1 0.55
6 0.142857
0 0.9
1 0.9
6 0.076923
0 0.678453453
0 0.1
2 0.31818
9 0.345678993
2 0.25
1 0.3
0 0.3
0 0.0
5 0.99999
6 0.714285
0 0.5
0 0.35
-1
``````
output:

Code: Select all

``````Case 1: 7/22
Case 2: 1/3
Case 3: 1/11
Case 4: 5/7
Case 5: 119047381/166666500
Case 6: 1/1
Case 7: 13717421/111111111
Case 8: 54869684/55555555
Case 9: 574454131/999999999
Case 10: 41888317/49999500
Case 11: 2/9
Case 12: 1/9
Case 13: 2/9
Case 14: 1/3
Case 15: 4/9
Case 16: 5/9
Case 17: 2/3
Case 18: 7/9
Case 19: 8/9
Case 20: 1/1
Case 21: 0/1
Case 22: 1/5
Case 23: 1/5
Case 24: 2000000/99999999
Case 25: 3/10
Case 26: 1/2
Case 27: 11/20
Case 28: 5/9
Case 29: 1/7
Case 30: 9/10
Case 31: 1/1
Case 32: 1/13
Case 33: 678453453/1000000000
Case 34: 1/10
Case 35: 7/22
Case 36: 38408777/111111111
Case 37: 25/99
Case 38: 1/3
Case 39: 3/10
Case 40: 0/1
Case 41: 1/1
Case 42: 5/7
Case 43: 1/2
Case 44: 7/20
``````

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<math.h>

int gcd(int p,int j)
{
int tmp;
while ( j != 0 )
{
tmp = p % j;
p = j;
j = tmp;
}
return p;
}

main()
{
int k,j;
int cases=1;
double den,nom;
int factor;
char in[12];
double num,product,loopNum;
int i;

while(scanf("%d",&j))
{
if(j==-1)
break;
scanf("%s",in);
num=0.0;
product=0.1;
for(i=2;i<strlen(in);i++,product*=0.1)
{
num+=(double)((in[i]-'0')*product);
}
k=strlen(in)-2-j;
loopNum=0.0;
product=0.1;
for(i=2+k;i<strlen(in);i++,product*=0.1)
{
loopNum+=(double)((in[i]-'0')*product);
}
nom=(double)(pow(10,k+j)*num-(pow(10,k)*num-loopNum));
den=(double)(pow(10,k+j)-pow(10,k));
if(j!=0)
factor=gcd((int)nom,(int)den);
else
{
nom=(double)(pow(10,k)*num);
den=(double)(pow(10,k));
factor=gcd((int)nom,(int)den);
}
nom/=(double)factor;
den/=(double)factor;
printf("Case %d: %0.lf/%0.lf\n",cases++,nom,den);
}
}
``````
I tried it, but it didn't work, cause my output met all the test cases above.
Could someone give me more tricky test cases.
Thanks you. ^^

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

### Why WA on P332

My solution gets WA on P332.
Here is code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long GCD (long long A, long long B) {
if (A == 0) return B;
return GCD (B%A, A);
}

int main (void) {
long long N = 0, A, B, J, K, P [10];
double X, Y;
char S [15];
P [0] = 1;
for (J = 1; J < 10; J++) P [J] = 10*P [J-1];
while (scanf ("%d", &J) != EOF) {
if (J == -1) break;
getc (stdin);
gets (S);
K = strlen (S)-2;
X = strtod (S, NULL);
A = P [K]*X-P [K-J]*X+1, B = P [K]-P [K-J];
A /= (K = GCD (A, B)), B /= K;
printf ("Case %d: %d/%d\n", ++N, A, B);
}
exit (0);
}``````
PLZ HELP.
Giorgi Lekveishvili

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
1/9 = 0.11111......

9 * 1/9 = 0.111111........ * 9
1 = 0.99999........