332 - Rational Numbers from Repeating Fractions

[Morning]

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]

[WR]

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]

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

[Morning]

I've gotten AC,thanks

[Wei]

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]

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

[someone1985]

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]

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.

[Sedefcho]

[Sedefcho]

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]

Of course yes, but now still got wrong answer haha

[Sedefcho]

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]

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]

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.

[roticv]

1/9 = 0.11111......

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