TopCoder SRM413 Div1Medium

InfiniteSequence.java

/**
 * @author Taketo Yoshida
 */
import java.util.*;

public class InfiniteSequence {
  private Solver solver;

  enum SolverType { DP, DFS, MEMODFS }
  class SolverNotFoundException extends Exception {
    public SolverNotFoundException(String msg) { super(msg); }
  }

  interface Solver {
    public long solve(long n, int p, int q);
  }

  /*
   * Dynamic Programming
   */
  class DpSolver implements Solver {
    public long solve(long n, int p, int q) {
      int a, b, tmpa, tmpb;
      int[] dp = new int[(int)n + 1];
      dp[0] = 1;
      for (int i = 1; i <= n; i++) {
        a = i / p;
        b = i / q;
        tmpa = (a <= 0) ? 1 : dp[a];
        tmpb = (b <= 0) ? 1 : dp[b];
        dp[i] = tmpa + tmpb;
      }
      return dp[(int)n];
    }
  }

  /*
   * Simple DFS
   */
  class DfsSolver implements Solver {
    public long solve(long n, int p, int q) {
      return (n <= 0) ? 1 : (solve(n/p, p, q) + solve(n/q, p, q));
    }
  }

  /*
   * Memorized DFS
   */
  class MemoDfsSolver implements Solver {
    private HashMap<Long, Long> map; 
    public MemoDfsSolver() {
      map = new HashMap<Long, Long>();
    }
    public long solve(long n, int p, int q) {
      map.clear();
      return rec(n, p, q);
    }
    public long rec(long n, int p, int q) {
      if (n <= 0) return 1;
      if (map.containsKey(n)) return map.get(n);
      long ret = (rec(n/p, p, q) + rec(n/q, p, q));
      map.put(n, ret);
      return ret;
    }
  }

  public InfiniteSequence(SolverType type) throws SolverNotFoundException {
    if (type == SolverType.DP) {
      solver = new DpSolver();
    } else if (type == SolverType.DFS) {
      solver = new DfsSolver();
    } else if (type == SolverType.MEMODFS) {
      solver = new MemoDfsSolver();
    } else {
      throw new SolverNotFoundException("this type is not found.");
    }
  }

  public static void main(String[] args) {
    double start = System.currentTimeMillis();
    try { (new InfiniteSequence(SolverType.MEMODFS)).runTest(-1); } catch(SolverNotFoundException e) {}
    double end = System.currentTimeMillis();
    System.out.println("time : " + (end - start) + "ms");
  }

  public void runTest(int testCase) {
    if ((testCase == -1) || (testCase == 0)) testCase0();
    if ((testCase == -1) || (testCase == 1)) testCase1();
    if ((testCase == -1) || (testCase == 2)) testCase2();
  }

  private void verifyCase(int testCase, long expected, long received) {
    System.err.println("Test Case #" + testCase + "...");
    if (expected == received) {
      System.err.println("PASSED"); 
    } else { 
      System.err.println("FAILED"); 
      System.err.println("\tExpected: \"" + expected + '\"');
      System.err.println("\tReceived: \"" + received + '\"');
    }
  }

  private void testCase0() {
    long Arg0 = 21L; int Arg1 = 3; int Arg2 = 5; 
    verifyCase(0, 7L, solver.solve(Arg0, Arg1, Arg2));
  }

  private void testCase1() {
    long Arg0 = 10000000000L; int Arg1 = 3; int Arg2 = 2; 
    verifyCase(1, 110809534L, solver.solve(Arg0, Arg1, Arg2));
  }

  private void testCase2() {
    long Arg0 = 10000000000000L; int Arg1 = 2; int Arg2 = 2;
    verifyCase(2, 17592186044416L, solver.solve(Arg0, Arg1, Arg2));
  }
}