Problem : Sloppy Fractions
Fractions are real numbers that can be written as a/b, where a and b are both integers, and b 6!= 0. We
will restrict ourselves to fractions that lie between 0 and 1, both inclusive. This means that 0 GT aLT b when
both a and b are non-negative. There are two ways of writing fractions: In the Canonical form, we write a
fraction as a/b where a and b are positive integers having no factor in common (except 1, of course). In the
Decimal form, brackets are placed around the smallest-sized left-most group of digits that repeats. Here
are some examples:
Fraction Canonical Decimal Full expansion
5/12 5/12 0.41(6) 0.41666666...
3/21 1/7 0.(142857) 0.142857142857142857...
1/5 1/5 0.2(0) 0.2000000...
7/8 7/8 0.875(0) 0.875000000...
3/9 1/3 0.(3) 0.3333333...
By convention, the Canonical form for fraction 0.0000 . . . will be 0/1.
Our protagonist is mathematician Chen, who prefers writing fractions in the Decimal form. Chen is
quite old — he celebrated his 100th birthday a fortnight ago. He’s become sloppy over the years. Since
his 90th birthday, he hasn’t necessarily been placing the brackets around the smallest-sized left-most group
of digits that repeats. For example, he might write 0.52(01) as 0.5201(01) or even as 0.52010101(0101).
Further, since his 100th birthday, he’s been forgetting to place the brackets around the repeating-groups!
This means that 0.520101 might denote any of the following: 0.52010(1), 0.5201(01), 0.520(101), 0.52(0101),
0.5(20101), 0.(520101) and 0.520101. Your goal is to write a program which will take a string written down
by Chen as input, and produce all possible fractions in Canonical form that string could correspond to.
Input: One string per line, of the form 0.a1a2 . . . a`, where 1 ` 6 and each of a1, a2 . . . a` is a digit
between 0 and 9.
Output: See the format below. Each fraction should be printed in the Canonical form. There should
be no duplicates. Fractions should be sorted by magnitude, smallest to largest. There should be exactly one
blank separating the fractions, and one blank before and after the = symbol, as shown below.
Input Output
0.000
0.3
0.32
0.99
0.511
0.5151
0.000 = 0/1
0.3 = 3/10 1/3
0.32 = 8/25 29/90 32/99
0.99 = 99/100 1/1
0.511 = 511/1000 23/45 511/999
0.5151 = 5151/10000 1159/2250 2573/4995 17/33
Saturday, June 27, 2009
Subscribe to:
Post Comments (Atom)
3 comments:
solution in c:
#include stdio.h
#include stdlib.h
double d[10] ;
int up[10], down[10] ;
int gcd (int a, int b)
{
int t ;
if (a*b == 0)
return 1 ;
while (a)
t=b%a, b=a, a=t ;
return b;
}
int value (char *s, int len)
{
int i, x=0 ;
for (i = 0; i < len; i++)
x=(x*10)+(s[i]-'0') ;
return x ;
}
int power (int x, int p)
{
int a = 1 ;
while (p)
a*=x, p-- ;
return a ;
}
void get_frac(int A, int B, int a, int b, int index)
{
int X = (b==0) ? A : A * (power(10,b) - 1) + B ;
int Y = (b==0) ? power(10,a) : power(10,a) * (power(10,b) - 1) ;
int g = gcd(X, Y) ;
if (X == 0)
Y = 1 ;
up[index] = X/g ;
down[index] = Y/g ;
d[index] = (up[index] * 1.0) / down[index] ;
return ;
}
void handle (char *s)
{
int i, j, A, B, up_tmp, down_tmp ;
double d_tmp ;
int slen = strlen (s) ;
for (i = 0; i <= slen; i++)
{
A = value (s, i) ;
B = value (s + i, slen-i) ;
get_frac (A,B,i, slen-i, i) ;
}
for (i = 0; i <= slen; i++)
for (j = 0; j < i; j++)
if (d[j] > d[i])
{
d_tmp=d[j], d[j]=d[i], d[i]=d_tmp ;
up_tmp=up[j], up[j]=up[i], up[i]=up_tmp;
down_tmp=down[j], down[j]=down[i], down[i]=down_tmp ;
}
fprintf (stdout, "0.%s =", s) ;
for (i = 0; i <= slen; i++)
if ((i == 0) || (up[i] != up[i-1]) || (down[i] != down[i-1]))
fprintf (stdout, " %d/%d", up[i], down[i]) ;
fprintf (stdout, "\n") ;
return ;
}
int main(int argc, char *argv[])
{
char s[10] ;
while (scanf ("%s", &s[0]) == 1)
handle (&s[2]) ;
return 0 ;
}
solution in JAVA:
import java.util.*;
import java.io.*;
public class Main implements Comparator {
int length;
long left, right, den, den2;
long n, d;
public int compare (Object a, Object b){
StringTokenizer st1 = new StringTokenizer ((String) a, "/");
StringTokenizer st2 = new StringTokenizer ((String) b, "/");
int x1 = Integer.parseInt (st1.nextToken());
int y1 = Integer.parseInt (st1.nextToken());
int x2 = Integer.parseInt (st2.nextToken());
int y2 = Integer.parseInt (st2.nextToken());
if (x1*y2 == x2*y1) return 0;
if (x1*y2 < x2*y1) return -1;
return 1;
}
public long gcd (long a, long b){
if (b == 0) return a;
return gcd (b, a % b);
}
public String frac (long n, long d){
long g = gcd (n, d);
// System.out.println (n + " " + d + " " + g);
n /= g;
d /= g;
return n + "/" + d;
}
public void run(){
try {
BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
String s;
while ((s = br.readLine()) != null){
s = s.substring (2);
length = s.length();
ArrayList arr = new ArrayList();
for (int i = 0; i <= length; i++){
if (i != length)
left = Long.parseLong (s.substring (0, length - i));
else
left = 0;
if (i == 0)
right = 0;
else
right = Long.parseLong (s.substring (length - i, length));
if (i == 0){ den = 1;
den2 = 1;
for (int j = 0; j < length - i; j++){
den2 *= 10;
}
}
else {
den = 0;
for (int j = 0; j < i; j++){
den = den * 10 + 9;
}
den2 = 1;
for (int j = 0; j < length - i; j++){
den *= 10;
den2 *= 10;
}
}
n = left * den + right * den2;
d = den * den2;
//System.out.println (left + " " + den2 + " " + right + " " + den + " " + n + " " + d);
String frac = frac (n, d);
if (!arr.contains (frac)) arr.add (frac);
}
Collections.sort (arr, this);
System.out.print ("0." + s + " =");
for (int i = 0; i < arr.size(); i++){
System.out.print (" " + (String) arr.get(i));
}
System.out.println();
}
br.close();
}
catch (Exception e){
e.printStackTrace();
}
}
public static void main (String args[]){
new Main().run();
}
}
solution in c++
#include iostream
#include string
#include set
using namespace std;
struct fract
{
uint64_t n,d;
void fix()
{
// euclid's alg
uint64_t a=n,b=d,c=20;
if(n==0) {d=1; return;}
while(c>0)
{
c=a%b;
a=b;
b=c;
}
n/=a;
d/=a;
}
fract(uint64_t n, uint64_t d) { this->n = n; this->d=d; fix(); }
bool operator == (const fract &x) const
{
return n==x.n && d==x.d;
}
bool operator < (const fract &x) const
{
return n*x.d < x.n*d;
}
};
int ten2(int n)
{
int x=1;
for(int i=0; iLTn; i++)
x=x*10;
return x;
}
void process(string s)
{
set(fract) fl;
string digs = s.substr(2);
for(unsigned i=0; i<=digs.length(); i++)
{
string t=digs.substr(0,i);
string r=digs.substr(i);
fract term(atoi(t.c_str()), ten2(i));
fract rep(atoi(r.c_str()), ten2(i)*(ten2(digs.length()-i)-1));
fract res = fract(rep.n*term.d + term.n*rep.d, rep.d*term.d);
/* if(res.d<1) {
printf("0.%s(%s) --> %d/%d\n", t.c_str(),r.c_str(),res.n,res.d);
printf("0.%s = %d/%d 0.[...]%s = %d/%d\n", t.c_str(), term.n,term.d,
r.c_str(), rep.n,rep.d);
}*/
fl.insert(fract(rep.n*term.d + term.n*rep.d, rep.d*term.d));
}
cout << s << " =";
for(set(fract)::iterator it = fl.begin(); it != fl.end(); it++)
cout << " " << it->n << "/" << it->d;
cout << endl;
}
int main()
{
while(cin)
{
string s;
cin >> s;
if(s.empty()) continue;
process(s);
}
return 0;
}
Post a Comment