TopCoder 練習

HanoiGoodAndBad(Member SRM 482 Div1 Medium)

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3.   
4. public class HanoiGoodAndBad{  
5.     LinkedList<Integer> a,b,c;  
6.     int dave;  
7.     int step;  
8.   
9.     public int moves(int n, int dave){  
10.         this.dave=dave;  
11.         a=new LinkedList<Integer>();  
12.         b=new LinkedList<Integer>();  
13.         c=new LinkedList<Integer>();  
14.         for(int i=0;i<n;i++)  
15.             a.addLast(i);  
16.         step=0;  
17.         solve(a,b,c,n);  
18.           
19.         //System.out.println(Arrays.toString(a.toArray()));  
20.         //System.out.println(Arrays.toString(b.toArray()));  
21.         //System.out.println(Arrays.toString(c.toArray()));  
22.   
23.         return rec(a,b,c,n-1);  
24.     }  
25.   
26.     int rec(LinkedList<Integer> a,LinkedList<Integer> b, LinkedList<Integer> c,int k){  
27.         if(a.contains(k))  
28.             return rec(a,b,c,k-1);  
29.         else if(b.contains(k))  
30.             return (int)Math.pow(3,k)+rec(c,b,a,k-1);  
31.         else if(c.contains(k))  
32.             return 2*(int)Math.pow(3,k)+rec(a,b,c,k-1);  
33.         else  
34.             return 0;  
35.     }  
36.   
37.     void solve(LinkedList<Integer> a,LinkedList<Integer> b, LinkedList<Integer> c, int k){  
38.         if(k==0)  
39.             return;  
40.         solve(a,c,b,k-1);  
41.         if(step==dave)  return;  
42.         c.addFirst(a.removeFirst());  
43.         step++;  
44.         if(step==dave)  return;  
45.         solve(b,a,c,k-1);  
46.     }  
47. }  

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);
    }
}