ACM International Collegiate Programming Contest, Japan Domestic, 2004, Problem C

gistfile1.java

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

/*
 * C.java
 *
 * Created on 2005/06/13, 12:25
 *
 * To change this template, choose Tools | Options and locate the template under
 * the Source Creation and Management node. Right-click the template and choose
 * Open. You can then make changes to the template in the Source Editor.
 */

/**
 *
 * @author kunishi
 */
public class C {
    int p, q, a, n;
    Rational target;
    int results = 0;
    
    public class Rational {
        int p, q;
        public Rational(int p, int q) {
            this.p = p;
            this.q = q;
        }
        public Rational add(Rational r) {
            if (r.q % q == 0) {
                return new Rational(r.p + p * (r.q / q), r.q);
            } else if (q % r.q == 0) {
                return new Rational(p + r.p * (q / r.q), q);
            } else {
                return new Rational(p * r.q + r.p * q, q * r.q);
            }
        }
        public boolean largerThan(Rational r) {
            return (p * r.q - q * r.p) > 0;
        }
        public boolean equals(Rational r) {
            return ((p * r.q - q * r.p) == 0);
        }
        public String toString() {
            return p + "/" + q;
        }
    }
    /** Creates a new instance of C */
    public C() {
    }
    
    public static void main(String[] args) {
        C c = new C();
        c.doCalc(args[0]);
    }
    
    public void doCalc(String infile) {
        try {
            BufferedReader br = new BufferedReader(new FileReader(infile));
            String s = br.readLine();
            while (!s.equals("0 0 0 0")) {
                String[] vals = s.split("\\s");
                p = Integer.parseInt(vals[0]);
                q = Integer.parseInt(vals[1]);
                a = Integer.parseInt(vals[2]);
                n = Integer.parseInt(vals[3]);
                target = new Rational(p, q);
                results = 0;
                doSum(new Rational(0, 1), 1, 0, 1);
                System.out.println(results);
                s = br.readLine();
            }
        } catch (FileNotFoundException e) {
            System.out.println(e);
        } catch (IOException e) {
            System.out.println(e);
        }
    }
    
    public void doSum(Rational sum, int proda, int sumn, int last) {
        if (proda > a || sumn > n) {
            return;
        } else if (sum.equals(target)) {
            results++;
            return;
        } else if (sum.largerThan(target)) {
            return;
        } else { // sum < p/q
            for (int i = last; i <= a/proda; i ++) {
                doSum(sum.add(new Rational(1, i)), proda*i, sumn+1, i);
            }
            return;
        }
    }
}