[백준] 9942번 하노이의 네 탑 (gold 2

import java.io.*;
import java.util.*;
import java.math.*;
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BigInteger[] num=new BigInteger[1001];
        BigInteger[] og=new BigInteger[1001];
        num[1]=new BigInteger("1");
        num[2]=new BigInteger("3");
        num[3]=new BigInteger("5");

        og[1]=new BigInteger("1");
        BigInteger mul=new BigInteger("2");
        BigInteger ad=new BigInteger("1");
        for(int i=2; i<num.length; i++){
            og[i]=new BigInteger(og[i-1].multiply(mul).add(ad).toString());
        }
        BigInteger min;
        BigInteger temp;
        for(int i=4; i<num.length; i++){
            min=new BigInteger(String.valueOf(Long.MAX_VALUE));
            temp=new BigInteger("0");
            for(int j=i/2; j<i; j++){
                temp=num[j].multiply(mul).add(og[i-j]);
                min=temp.compareTo(min)<=0 ? temp:min;
            }
            num[i]=new BigInteger(min.toString());

        }
        long index=1;
        String input;
        while((input=br.readLine())!=null && input.length()!=0){
            int n=Integer.valueOf(input);
            bw.write("Case "+index+": "+num[n]+"\n");
            index++;
        }
        bw.flush();


    }
}