Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.math.BigInteger;
- import java.util.HashMap;
- public class BytelandianMaxSum {
- private static HashMap<BigInteger, BigInteger> memory = new HashMap<BigInteger, BigInteger>();
- // The idea is to increase readability in the changer method and improve(?)
- // performance due to not constantly having to create new BigIntegers with
- // the same values
- public static final BigInteger FOUR = new BigInteger("4");
- public static final BigInteger THREE = new BigInteger("3");
- public static final BigInteger TWO = new BigInteger("2");
- public static void main(String[] args) {
- memory.put(new BigInteger("0"), new BigInteger("0"));
- BigInteger target = new BigInteger("100000000");
- System.out.println("The maximal value of " + target + " is "
- + changer(target).toString());
- }
- private static BigInteger changer(BigInteger coin) {
- if (memory.get(coin) != null) {
- return memory.get(coin);
- }
- BigInteger tmp = changer(coin.divide(FOUR)).add(
- changer(coin.divide(THREE)).add(changer(coin.divide(TWO))));
- return (tmp.compareTo(coin) == 1) ? tmp : coin;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement