TopCoder 練習

HanoiGoodAndBad(Member SRM 482 Div1 Medium)

LayCurseさんのブログ
ゲームにっき(仮) | SRM482 DIV1 参加記録:
を参考に解く．

import java.util.*;
import java.lang.*;

public class HanoiGoodAndBad{
    LinkedList<Integer> a,b,c;
    int dave;
    int step;

    public int moves(int n, int dave){
        this.dave=dave;
        a=new LinkedList<Integer>();
        b=new LinkedList<Integer>();
        c=new LinkedList<Integer>();
        for(int i=0;i<n;i++)
            a.addLast(i);
        step=0;
        solve(a,b,c,n);
        
        //System.out.println(Arrays.toString(a.toArray()));
        //System.out.println(Arrays.toString(b.toArray()));
        //System.out.println(Arrays.toString(c.toArray()));

        return rec(a,b,c,n-1);
    }

    int rec(LinkedList<Integer> a,LinkedList<Integer> b, LinkedList<Integer> c,int k){
        if(a.contains(k))
            return rec(a,b,c,k-1);
        else if(b.contains(k))
            return (int)Math.pow(3,k)+rec(c,b,a,k-1);
        else if(c.contains(k))
            return 2*(int)Math.pow(3,k)+rec(a,b,c,k-1);
        else
            return 0;
    }

    void solve(LinkedList<Integer> a,LinkedList<Integer> b, LinkedList<Integer> c, int k){
        if(k==0)
            return;
        solve(a,c,b,k-1);
        if(step==dave)  return;
        c.addFirst(a.removeFirst());
        step++;
        if(step==dave)  return;
        solve(b,a,c,k-1);
    }
}