Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Mar 6th, 2013  |  syntax: Java  |  size: 1.09 KB  |  views: 40  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.math.BigInteger;
  2. import java.util.HashMap;
  3.  
  4. public class BytelandianMaxSum {
  5.         private static HashMap<BigInteger, BigInteger> memory = new HashMap<BigInteger, BigInteger>();
  6.  
  7.         // The idea is to increase readability in the changer method and improve(?)
  8.         // performance due to not constantly having to create new BigIntegers with
  9.         // the same values
  10.        
  11.         public static final BigInteger FOUR = new BigInteger("4");
  12.         public static final BigInteger THREE = new BigInteger("3");
  13.         public static final BigInteger TWO = new BigInteger("2");
  14.  
  15.         public static void main(String[] args) {
  16.                 memory.put(new BigInteger("0"), new BigInteger("0"));
  17.                 BigInteger target = new BigInteger("100000000");
  18.                 System.out.println("The maximal value of " + target + " is "
  19.                                 + changer(target).toString());
  20.  
  21.         }
  22.  
  23.         private static BigInteger changer(BigInteger coin) {
  24.                 if (memory.get(coin) != null) {
  25.                         return memory.get(coin);
  26.                 }
  27.                 BigInteger tmp = changer(coin.divide(FOUR)).add(
  28.                                 changer(coin.divide(THREE)).add(changer(coin.divide(TWO))));
  29.                 return (tmp.compareTo(coin) == 1) ? tmp : coin;
  30.         }
  31.  
  32. }
clone this paste RAW Paste Data