fork download
copy 
  1. import java.math.BigInteger;
  2. import java.util.ArrayList;
  3. import java.util.HashMap;
  4. import java.util.List;
  5. import java.util.Map;
  6.  
  7. public class Main {
  8.   private final int nChars;
  9.   private int count = 0;
  10.   private Map<Task,BigInteger> memo = new HashMap<>();
  11.  
  12.   public Main(int nChars) {
  13.     this.nChars = nChars;
  14.   }
  15.   /*+******************************************************************/  
  16.   private static class Task {
  17.     public final int strlen;
  18.     public final int unpaired;
  19.  
  20.     Task(int strlen, int unpaired) {
  21.       this.strlen = strlen;
  22.       this.unpaired = unpaired;
  23.     }
  24.     @Override
  25.     public int hashCode() {
  26.       return strlen*117 ^ unpaired;
  27.     }
  28.     @Override
  29.     public boolean equals(Object other) {
  30.       if (!(other instanceof Task)) {
  31.         return false;
  32.       }
  33.       Task t2 = (Task)other;
  34.       return strlen==t2.strlen && unpaired==t2.unpaired;
  35.     }
  36.     @Override
  37.     public String toString() {
  38.       return "("+strlen+","+unpaired+")";
  39.     }
  40.   }
  41.   /*+******************************************************************/  
  42.   private BigInteger getMemoed(Task t) {
  43.     //System.out.println("getMemoed"+t);
  44.     if (t.strlen==0 || t.unpaired<0 || t.unpaired>t.strlen || t.unpaired>nChars
  45.         || t.strlen%2 != t.unpaired%2) {
  46.       return BigInteger.valueOf(0);
  47.     }
  48.  
  49.     if (t.strlen==1) {
  50.       return BigInteger.valueOf(nChars);
  51.     }
  52.     return memo.get(t);
  53.   }
  54.   /*+******************************************************************/  
  55.   public int getCount() {
  56.     return count;
  57.   }
  58.   public BigInteger computeNDeep(Task t) {
  59.     List<Task> stack = new ArrayList<Task>();
  60.     BigInteger result = null;
  61.     stack.add(t);
  62.  
  63.     while (stack.size()>0) {
  64.       count += 1;
  65.       t = stack.remove(stack.size()-1);
  66.       //System.out.println("removed "+t);
  67.       result = getMemoed(t);
  68.       if (result!=null) {
  69.         continue;
  70.       }
  71.  
  72.       Task t1 = new Task(t.strlen-1, t.unpaired+1);
  73.       BigInteger r1 = getMemoed(t1);
  74.       Task t2 = new Task(t.strlen-1, t.unpaired-1);
  75.       BigInteger r2 = getMemoed(t2);
  76.       if (r1==null) {
  77.         stack.add(t);
  78.         stack.add(t1);
  79.         if (r2==null) {
  80.           stack.add(t2);
  81.         }
  82.         continue;
  83.       }
  84.       if (r2==null) {
  85.         stack.add(t);
  86.         stack.add(t2);
  87.         continue;
  88.       }
  89.       result = compute(t1.unpaired, r1, nChars-t2.unpaired, r2);
  90.       memo.put(t,  result);
  91.       //System.out.println(""+t1+":"+r1+", "+t2+":"+r2+"  memo "+t+" = "+result);
  92.     }
  93.     return result;
  94.   }
  95.   private BigInteger compute(int u1, BigInteger r1, int u2, BigInteger r2) {
  96.     r1 = r1.multiply(BigInteger.valueOf(u1));
  97.     r2 = r2.multiply(BigInteger.valueOf(u2));
  98.     return r1.add(r2);
  99.   }
  100.   public static void main(String[] argv) {
  101.     argv = new String[] {"500", "4"};
  102.     int strlen = Integer.parseInt(argv[0]);
  103.     int nChars = Integer.parseInt(argv[1]);
  104.  
  105.     Main eps = new Main(nChars);
  106.  
  107.     BigInteger result = eps.computeNDeep(new Task(strlen, 0));
  108.     System.out.printf("%d: N(%d, %d, 0) = %d%n", 
  109.                       eps.getCount(), strlen, nChars, 
  110.                       result); 
  111.   }
  112. }
  113.  
Success #stdin #stdout 0.12s 320320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2236: N(500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360
https://ideone.com/KvB5Jv
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!