2010年9月18日土曜日

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

0 件のコメント: