import java.io.*; import java.util.*; // LInt: // 整数のリスト // キューやスタックとして使うのに便利なメソッドを幾つか class LInt extends ArrayList { LInt() { super(); } LInt( List x ) { super(x); } LInt getF(int n) { try{return new LInt(subList(0,n));} finally{removeRange(0,n);} } void putF(LInt o) { addAll(0, o.rev()); } void putB(LInt o) { addAll(o); } LInt sort() { Collections.sort(this); return this; } LInt rev() { Collections.reverse(this); return this; } } // State: // Q, A, B の状態を表すクラス // 普通にそれぞれをリストとして持っているだけです class State { // 直前の操作 int p = 0; // 初期化処理 : コピーまたはqのリストから作る LInt q, a, b; State( State o ) {q = new LInt(o.q); a = new LInt(o.a); b = new LInt(o.b);} State( LInt o ) {q = new LInt(o); a = new LInt(); b = new LInt();} // HashSetに突っ込みたいのでその辺 public int hashCode() { return (q.hashCode()<<2) ^ (a.hashCode()) ^ (b.hashCode()>>2); } public boolean equals( Object o ) { State s = (State) o; return q.equals(s.q) && a.equals(s.a) && b.equals(s.b); } // 各種基本操作: 超破壊的 State QA(int n) { a.putF( q.getF(n) ); p=1; return this; } State QB(int n) { b.putF( q.getF(n) ); p=2; return this; } State QQ(int n) { q.putB( q.getF(n) ); p=3; return this; } State AQ(int n) { q.putB( a.getF(n) ); p=4; return this; } State AB(int n) { b.putF( a.getF(n) ); p=5; return this; } State BQ(int n) { q.putB( b.getF(n) ); p=6; return this; } State BA(int n) { a.putF( b.getF(n) ); p=7; return this; } void revQ() { q.rev(); } // 便利メソッド boolean isGoal() { if( !a.isEmpty() || !b.isEmpty() ) return false; for(int i=1,e=q.size(); i q.get(i) ) return false; return true; } int estimateSteps() { int steps = 0; for(int i=1; i goal = new HashSet(); DFS bwd = new DFS() { void visit( State s ) { s.revQ(); goal.add(s); }}; bwd.dfs( BWD_STEPS, bwd_start ); // 再び反復深化で、4ステップ集合に入るかどうかを見つける fwd = new DFS() { void visit( State s ) { if( goal.contains(s) ) throw new Found(); } boolean impossible( int d, State s ) { return s.estimateSteps() > d+BWD_STEPS; } }; for(int i=0;; ++i) try { fwd.dfs(i, fwd_start); } catch( Found e ) { return i+BWD_STEPS; } } }