import java.util.HashMap;

public class SpeedComparison {

    private static HashMap<Long, Long> memory = new HashMap<Long, Long>();
    private static HashMap<Long, Long> map = new HashMap<Long, Long>();
    public static final long LOWER_BOUND = 10_000_000_000L;
    public static final long UPPER_BOUND = 10_001_000_000L;


    public static void main(String[] args) {
        memory.put(0L, 0L);
        long time1 = System.currentTimeMillis();
        for(long i = LOWER_BOUND; i <= UPPER_BOUND; i++){
            changer(i);
        }
        long time2 = System.currentTimeMillis();
        for(long i = LOWER_BOUND; i <= UPPER_BOUND; i++){
            coins(i);
        }
        long time3 = System.currentTimeMillis();

        System.out.println("changer needed " + (time2 - time1) + " milliseconds");
        System.out.println("coins needed " + (time3 - time2) + " milliseconds");
        double changerTime = (time2 - time1);
        double coinsTime = (time3 - time2);
        System.out.println("the speed ratio changer/coins is: " + (changerTime/coinsTime));
    }


    public static Long changer(long coin) {
        if (!memory.containsKey(coin)){
            long tmp = changer(coin/4L) + changer(coin/3L) + changer(coin/2L);
            memory.put(coin, tmp > coin ? tmp : coin);
        }

        return memory.get(coin);
    }

    public static long coins(long n) {
        if (!map.containsKey(n)) {
            map.put(n, (n > (n / 2) + (n / 3) + (n / 4) ? n : coins(n / 2)
                    + coins(n / 3) + coins(n / 4)));
        }
        return map.get(n);
    }

}