読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0503

contest contest-aoj language language-c++11

少し考えれば一番下のものを順番に移動していくしかないことがわかります。
置く場所を#0,#1,#2としてgoalを#0に固定する。1〜nまでのコップが順に並んだものが

  • #0にあるとき

=> 0

  • #1にあるとき

=> 3^n

  • #2にあるとき

=> 2*3^n
したがって下のコードのように再帰でかけるでしょう。あとはコップの配置をbitで表して右シフトで一番小さいコップから順に処理すればよいでしょう。

int p[20];

int f(int a, int b, int c)
{
  if(!b&&!c) return 0;
  int s = (a|b|c)>>1;
  int t = 0;
  while(s&1) {t++;s>>=1;}
  if(1&a) return f(a>>1,b>>1,c>>1);
  if(1&b) return f(c>>1,b>>1,a>>1)+p[t];
  if(1&c) return f(a>>1,b>>1,c>>1)+2*p[t];
}

int main()
{
  int n,m;
  p[0] = 1;
  FOR(i,1,20)
  {
    p[i] = p[i-1]*3;
  }
  while(cin >> n >> m,n)
  {
    int a[3] = {0};
    REP(i,3)
    {
      int t,u; cin >> t;
      REP(j,t)
      {
        cin >> u;
        a[i] |= 1 << u-1;
      }
    }
    int ans = min(f(a[0],a[1],a[2]),f(a[2],a[1],a[0]));
    cout << (ans>m?-1:ans) << endl;
  }
}