Problem:


大きさが異なる n 個のコップと 3 つのトレイ（お盆）A，B，C があり，それらのコップは 3 つのトレイの上にそれぞれ何個かずつ一山に重ねて置かれている．ただし，どのトレイにおいても，そのトレイの中で一番小さいコップが一番下に， 2 番目に小さいコップがその上に， 3 番目に小さいコップがその上にと，小さい順に伏せて重ねてある．例えば，下図の右側は， n = 5 個のコップがトレイ A，B，C にそれぞれ 2 個，0 個，3 個重ねて置かれている状態を示している．

このように，コップの初期状態が与えられたとき，次の規則 1 〜 3 を守りながら，すべてのコップを A または C のどちらかのトレイに移動させるには何回移動を行えばよいかを求めたい．

（規則 1） 1 回に 1 つのコップだけを移動させることができる．それは，そのトレイにあるコップの中で一番上のコップ（つまり，一番大きいコップ）である．

（規則 2）大きいコップの上に小さいコップを重ねてはいけない．

（規則 3）コップ 1 個の直接移動は，トレイ A から B，B から A，B から C，C から B のみが許され， A から C への直接移動や C から A への直接移動は許されない．

　n 個のコップの初期状態と整数 m が与えられたとき， m 回以内の移動で， A または C のどちらかのトレイにすべてのコップをまとめて重ねることができるかどうかを判定し，可能な場合には移動回数の最小値を，不可能な場合には -1 を出力するプログラムを作成しなさい．

　入力ファイルの 1 行目には， n と m がこの順に空白を区切り文字として書いてある． 1 ≦ n ≦ 15 であり， 1 ≦ m ≦ 15000000 である． 2 行目，3 行目，4 行目には， 1 から n までの整数を何個かずつ 3 つのグループに分けて，それぞれのグループ内で小さい順（昇順）に並べたものが書いてある．ただし，各行の先頭（それらの整数の前）には，それらの個数が書いてある． 2 行目に書かれている整数（先頭の 1 つを除く）はトレイ A の上に重ねられている各コップの大きさを表す．同様に， 3 行目に書かれている整数（先頭の 1 つを除く）はトレイ B の上に重ねられている各コップの大きさを表し， 4 行目に書かれている整数（先頭の１つを除く）はトレイ C の上に重ねられている各コップの大きさを表す． 

 

  入力例１
  入力例２
  入力例３
  入力例４

 

3 104 20 2 53 3

02 1 22 1 20

1 11 301 1

2 2 31 402 2 3

  　

  出力例１
  出力例２

  出力例３
  出力例４

930-1

入力

入力は複数のデータセットからなる．n, m がともに 0 のとき入力が終了する．データセットの数は 5 を超えない．

出力

データセットごとに、移動回数または -1 を１行に出力する．

入力例

3 10
0
1 1
2 2 3
4 20
2 1 2
1 3
1 4
2 5
2 1 2
0
0
3 3
0
1 1
2 2 3
0 0

出力例

9
3
0
-1

各データセットの出力（移動回数または -1）の後に改行を入れること． 

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3 10
0
1 1
2 2 3
4 20
2 1 2
1 3
1 4
2 5
2 1 2
0
0
3 3
0
1 1
2 2 3
0 0


Sample output:
9
3
0
-1

Submission status: Wrong Answer

Solution code:
INF = 10 ** 20

full_move1_memo = [None] * 100
full_move2_memo = [None] * 100
def full_move1(n):
  if n == 1:
    return 2
  if full_move1_memo[n]:
    return full_move1_memo[n]
  a = full_move1(n - 1) * 3 + 2
  full_move1_memo[n] = a
  return a

def full_move2(n):
  if n == 1:
    return 2
  if full_move2_memo[n]:
    return full_move2_memo[n]
  a = full_move2(n - 1) * 2 + 2
  full_move2_memo[n] = a
  return a

def half_move(n):
  if n == 1:
    return 1
  if full_move1_memo[n - 1]:
    return full_move1_memo[n - 1] + 1
  return  full_move1(n - 1) + 1

def solve():
  while True:
    n, m = map(int, input().split())
    if not n:
      break

    lst = [list(map(int,input().split()))[1:] for _ in range(3)]
    inds = [-1 for i in range(n)]

    for i in range(3):
      for j in lst[i]:
        inds[j - 1] = i
    
    ans = INF
    for pos in [0, 2]:
      rec = 0
      for i in range(n):
        pi = inds[i]
        if abs(pi - pos) == 2:
          rec += full_move2(n - i)
          pass
        elif abs(pi - pos) == 1:
          rec += half_move(n - i)
          pos = (pos + 2) % 4
      if rec < ans:
        ans = rec

    if ans <= m:
      print(ans)
    else:
      print(-1)

solve()

Submission status: Memory Limit Exceeded

Solution code:
import collections

while 1:
    src_dsts = [(0, 1), (1, 0), (1, 2), (2, 1)]
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    cupss = tuple([tuple(map(int, raw_input().split())[1:]) for i in range(3)])
    dones = set()
    q = collections.deque()
    q.append((0, cupss))
    while q:
        s, cupss = q.popleft()
        if s > m:
            continue
        if cupss in dones:
            continue
        dones.add(cupss)
        if len(cupss[0]) == n or len(cupss[2]) == n:
            print s
            break
        for src, dst in src_dsts:
           if len(cupss[src]) > 0:
                if len(cupss[dst]) == 0 or cupss[dst][-1] < cupss[src][-1]:
                    next = list(cupss)
                    next[dst] = cupss[dst] + (cupss[src][-1],)
                    next[src] = cupss[src][:-1]
                    q.append((s + 1, tuple(next)))
    else:
        print -1

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, input().split())
    if not n:
        break

    dest = [0] * n
    for tray in range(3):
        itr = map(int, input().split())
        next(itr)
        for i in itr:
            dest[i - 1] = tray

    cnt = 0
    current_tray = 0
    for i, tray in enumerate(dest):
        move = abs(tray - current_tray)
        if move == 1:
            cnt += 3 ** (n - i - 1)
            current_tray = abs(current_tray - 2)
        elif move == 2:
            cnt += 2 * 3 ** (n - i - 1)

    ans = min(cnt, 3 ** n - cnt - 1)
    print(ans if ans <= m else -1)

Submission status: Accepted

Solution code:
while True:
  try:
    n,m = map(int,input().split())
    l = [0 for i in range(n)]

    for i in range(3):
      s = list(map(int,input().split()))
      for j in s[1:]:
        l[j - 1] = i
    ans = 100000000
    for pos in [0,2]:
      count = 0
      for i in range(n):
        if abs(l[i] - pos) == 2:
          count += 2 * 3 ** (n - i - 1)
        elif pos == 1 and l[i] == 0:
          count += (3 ** (n - i - 1) - 1) // 2
          pos = 2
        elif pos == 1 and l[i] == 2:
          count += (3 ** (n - i - 1) - 1) // 2
          pos = 0
        elif pos == 0 and l[i] == 1:
          count += 3 ** (n - i - 1)
          pos = 2
        elif pos == 2 and l[i] == 1:
          count += 3 ** (n - i - 1)
          pos = 0
      ans = min(count,ans)
    if (ans <= m):
      print(ans)
    else:
      print(-1)
  except EOFError:
    break

Submission status: Accepted

Solution code:
INF = 10 ** 20

full_move1_memo = [None] * 16
full_move2_memo = [None] * 16

def full_move1(n):
  if n == 1:
    return 2
  if full_move1_memo[n]:
    return full_move1_memo[n]
  a = full_move1(n - 1) * 3 + 2
  full_move1_memo[n] = a
  return a

def full_move2(n):
  if n == 1:
    return 2
  if full_move2_memo[n]:
    return full_move2_memo[n]
  a = full_move1(n - 1) * 2 + 2
  full_move2_memo[n] = a
  return a

def half_move(n):
  if n == 1:
    return 1
  if full_move1_memo[n - 1]:
    return full_move1_memo[n - 1] + 1
  return full_move1(n - 1) + 1

def solve():
  while True:
    n, m = map(int, input().split())
    if not n:
      break

    lst = [list(map(int,input().split()))[1:] for _ in range(3)]
    inds = [-1 for i in range(n)]

    for i in range(3):
      for j in lst[i]:
        inds[j - 1] = i
    
    ans = INF
    for p in [0, 2]:
      rec = 0
      for i in range(n):
        pi = inds[i]
        if abs(pi - p) == 2:
          rec += full_move2(n - i)
        elif abs(pi - p) == 1:
          rec += half_move(n - i)
          p = (p + 2) % 4
      if rec < ans:
        ans = rec

    if ans <= m:
      print(ans)
    else:
      print(-1)

solve()

Submission status: Accepted

Solution code:
# AOJ 0503: Cup
# Python3 2018.6.29 bal4u

p3, c = [1]*16, [0]*16

for i in range(1, 16): p3[i] = 3*p3[i-1]
while True:
	n, m = map(int, input().split())
	if n == 0: break
	for i in range(3):
		a = list(map(int, input().split()))
		for j in range(a[0]): c[a[j+1]-1] = i
	ans = k = 0;
	for i in range(n):
		j = c[i]-k
		if j < 0: j = -j
		ans += j*p3[n-i-1]
		if j == 1: k = 2-k
	k = p3[n]-ans-1
	if ans > k: ans = k
	print(ans if ans <= m else -1)

Submission status: Accepted

Solution code:
from collections import deque

ans = []
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break

    state = 0
    for i in range(3):
        _, *cups = map(int, input().split())
        for cup in cups:
            state += i * 3**(cup-1)
    res = -1
    d = [-1] * 3**n
    que = deque([state])
    d[state] = 0
    while que:
        state = que.popleft()
        if state == 0 or state == 3**n - 1:
            res = d[state]
            break
        if d[state] > m:
            break

        state_copy = state
        tops = [-1] * 3
        for cup in range(n):
            tray = state_copy % 3
            state_copy //= 3
            tops[tray] = cup
        dt = [[1], [-1, 1], [-1]]
        for i, top in enumerate(tops):
            if top != -1:
                for di in dt[i]:
                    if top > tops[i + di]:
                        next_state = state + di * 3**top
                        if d[next_state] == -1:
                            d[next_state] = d[state] + 1
                            que.append(next_state)
    ans.append(res)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0503

def main():
    from collections import deque
    while True:
        N, M = map(int, input().split())
        if N == 0 and M == 0:
            return
        cop = [list(map(int, input().split())) for _ in range(3)]
        cop = [cop[0][1:]] + [cop[1][1:]] + [cop[2][1:]] + [0] + [-1]
        q = deque([cop])
        cnt = 0
        while q:
            lst = q.popleft()
            # a->b, b->a, b->c, c->bの4手が可能
            a = lst[0][-1] if lst[0] else 0
            b = lst[1][-1] if lst[1] else 0
            c = lst[2][-1] if lst[2] else 0
            a_cops = lst[0]
            b_cops = lst[1]
            c_cops = lst[2]
            cnt = lst[3]
            last = lst[4]
            if (lst[1] + lst[2] == []) or (lst[0] + lst[1] == []):
                print(cnt)
                break
            if cnt > M:
                print(-1)
                break
            if a > b and last != 1:
                nq = [a_cops[:-1]] + [b_cops + [a]] + [c_cops] + [cnt + 1] + [0]
                q.append(nq)
            if b > a and last != 0:
                nq = [a_cops + [b]] + [b_cops[:-1]] + [c_cops] + [cnt + 1] + [1]
                q.append(nq)
            if b > c and last != 3:
                nq = [a_cops] + [b_cops[:-1]] + [c_cops + [b]] + [cnt + 1] + [2]
                q.append(nq)
            if c > b and last != 2:
                nq = [a_cops] + [b_cops + [c]] + [c_cops[:-1]] + [cnt + 1] + [3]
                q.append(nq)


main()

Submission status: Accepted

Solution code:
def biggest_cup(s,v):
    try:
        return s.index(v)
    except ValueError:
        return 127

def neighbors(s):
    a = biggest_cup(s,0)
    b = biggest_cup(s,1)
    c = biggest_cup(s,2)
    if b > a:
        t = list(s)
        t[a] = 1
        yield tuple(t)
    elif b < a:
        t = list(s)
        t[b] = 0
        yield tuple(t)
    if c > b:
        t = list(s)
        t[b] = 2
        yield tuple(t)
    elif c < b:
        t = list(s)
        t[c] = 1
        yield tuple(t)


def solve_bfs(s0, m):
    n = len(s0)
    visited = {s0}
    q = [s0]
    for i in range(m+1):
        nq = []
        for s in q:
            if all(v == 0 for v in s) or all(v == 2 for v in s):
                return i
            for t in neighbors(s):
                if t not in visited:
                    visited.add(t)
                    nq.append(t)
        q = nq
    return -1


def solve_optimized(s0, m):
    qq = []
    q = [s0]
    for i in range(m+1):
        nq = []
        for s in q:
            if all(v == 0 for v in s) or all(v == 2 for v in s):
                return i
            for t in neighbors(s):
                if t not in qq:
                    nq.append(t)
        qq,q = q,nq
    return -1

if __name__ == '__main__':
    while True:
        n,m = map(int,input().split())
        if n == m == 0:
            break
        s = [None]*n
        for i in map(int,input().split()[1:]):
            s[-i] = 0
        for i in map(int,input().split()[1:]):
            s[-i] = 1
        for i in map(int,input().split()[1:]):
            s[-i] = 2
        print(solve_optimized(tuple(s), m))

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0503

from collections import deque

def main():
    N, M = map(int, input().split()) # N: コップの数　M: 最大回数
    if N==0:
        exit()
    data = [0]*N
    map(int, input().split())
    for b in list(map(int, input().split()))[1:]:
        data[N-b]=1
    for c in list(map(int, input().split()))[1:]:
        data[N-c]=2

    next_set = deque([(data[:],0)])
    visit=set([tuple(data)])

    while next_set:
        q = next_set.popleft()
        data, t = q
        l = data[0]

        # M 回より大きい回数かかる場合は-1
        if t > M:
            return -1

        # 全てのコップがA(あるいはC)にいるとき、時刻を返す
        for cnt, k in enumerate(data):
            if k != l:
                break
            if cnt == N-1 and k != 1:
                return t
            l = k

        pos = [N,N,N]
        k = 0
        for i, ABC in enumerate(data):
            if pos[ABC] == N:
                pos[ABC] = i
                k += 1
            if k == 3:
                break

        if pos[0] < pos[1]:
            data[pos[0]] = 1
            t_data = tuple(data)
            if t_data not in visit:
                next_set.append((data[:],t+1))
                visit.add(t_data)
            data[pos[0]] = 0
        else:
            data[pos[1]] = 0
            t_data = tuple(data)
            if t_data not in visit:
                next_set.append((data[:],t+1))
                visit.add(t_data)
            data[pos[1]] = 1

        if pos[1] < pos[2]:
            data[pos[1]] = 2
            t_data = tuple(data)
            if t_data not in visit:
                next_set.append((data[:],t+1))
                visit.add(t_data)
            data[pos[1]] = 1
        else:
            data[pos[2]] = 1
            t_data = tuple(data)
            if t_data not in visit:
                next_set.append((data[:],t+1))
                visit.add(t_data)
            data[pos[2]] = 2


while True:
    print(main())






'''

3 10
0
1 1
2 2 3

'''

Submission status: Accepted

Solution code:
from collections import deque

def search(x):
    for a in A[1:]:
        if x == a: return 'A'
    for b in B[1:]:
        if x == b: return 'B'
    for c in C[1:]:
        if x == c: return 'C'

while 1:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    s = ''
    for i in range(1, n+1):
        s += search(i) 
    d = {}
    d[s] = 0
    q = deque([s])
    cnt = 0
    while q:
        s = q.popleft()
        if d[s] > m:
            continue
        if s in ['A' * n, 'C' * n]:
            print(d[s])
            break
        lastA, lastB, lastC = -1, -1, -1
        for i in reversed(range(n)):
            if s[i] == 'A' and lastA < 0:
                lastA = i
            if s[i] == 'B' and lastB < 0:
                lastB = i
            if s[i] == 'C' and lastC < 0:
                lastC = i
        if lastA > lastB:
            news = s[:lastA] + 'B' + s[lastA+1:]
            if news not in d:
                d[news] = d[s] + 1
                q.append(news)
        if lastB > lastA:
            news = s[:lastB] + 'A' + s[lastB+1:]
            if news not in d:
                d[news] = d[s] + 1
                q.append(news)
        if lastB > lastC:
            news = s[:lastB] + 'C' + s[lastB+1:]
            if news not in d:
                d[news] = d[s] + 1
                q.append(news)
        if lastC > lastB:
            news = s[:lastC] + 'B' + s[lastC+1:]
            if news not in d:
                d[news] = d[s] + 1
                q.append(news)
    else:
        print(-1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque


def main():
    while True:
        N, M = map(int, readline().rstrip().split())
        if N == M == 0:
            break
        _, *A = map(int, readline().rstrip().split())
        _, *B = map(int, readline().rstrip().split())
        _, *C = map(int, readline().rstrip().split())

        A = [0] + A
        B = [0] + B
        C = [0] + C
        N += 1

        que = deque([(A, B, C, 0, -1)])   # pre: 1: A->B, 2: B->A, 3: B->C, 4: C->B
        res = -1
        while que:
            A, B, C, t, pre = que.popleft()
            if t > M:
                break
            if len(A) == N or len(C) == N:
                res = t
                break
            
            # A -> B
            if A[-1] > B[-1] and pre != 2:
                que.append((A[:-1], B + [A[-1]], C, t + 1, 1))

            # B -> A
            if B[-1] > A[-1] and pre != 1:
                que.append((A + [B[-1]], B[:-1], C, t + 1, 2))
            
            # B -> C
            if B[-1] > C[-1] and pre != 4:
                que.append((A, B[:-1], C + [B[-1]], t + 1, 3))
            
            # C -> B
            if C[-1] > B[-1] and pre != 3:
                que.append((A, B + [C[-1]], C[:-1], t + 1, 4))
            

        print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from math import log2
ans = []
while True:
    N, M = map(int, input().split())
    if (N,M) == (0,0):
        break
    a,b,c = 0,0,0
    for i in range(3):
        A = list(map(int, input().split()))
        if A[0]!=0:
            if i==0:
                for j in range(A[0]):
                    a += 1<<(A[1+j]-1)
            elif i==1:
                for j in range(A[0]):
                    b += 1<<(A[1+j]-1)
            else:
                for j in range(A[0]):
                    c += 1<<(A[1+j]-1)

    d = deque([(0,a,b,c,'')])

    while len(d)>0:
        cnt,a,b,c,prev = d.popleft()
        if cnt>M:
            ans.append(-1)
            break
        if a+b==0 or b+c==0:
            ans.append(cnt)
            break
        if a==0:
            amax = -1
        else:
            amax = int(log2(a))
        if b==0:
            bmax = -1
        else:
            bmax = int(log2(b))
        if c==0:
            cmax = -1
        else:
            cmax = int(log2(c))
        if amax>bmax and prev!='ba':
            d.append((cnt+1,a-(1<<amax),b+(1<<amax),c,'ab'))
        elif amax<bmax and prev!='ab':
            d.append((cnt+1,a+(1<<bmax),b-(1<<bmax),c,'ba'))
        if cmax>bmax and prev!='bc':
            d.append((cnt+1,a,b+(1<<cmax),c-(1<<cmax),'cb'))
        elif cmax<bmax and prev!='cb':
            d.append((cnt+1,a,b-(1<<bmax),c+(1<<bmax),'bc'))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque


def l2t(g):
    return tuple(map(tuple,g))




class BFS():
    def __init__(self, graph, m, n):
        # 盤面
        self.graph = graph
        self.m = m
        self.n = n
        # 始点からの距離
        self.dist = {}
        # キュー
        self.que = deque()

        self.eg_arr = [[[i for i in range(1,self.n+1)],[],[]],
                       [[],[],[i for i in range(1,self.n+1)]]]

    def list2num(self,g):
        str_ = ''
        for i in range(self.n):
            if i+1 in g[0]:
                str_ += '0'
            elif i+1 in g[1]:
                str_ += '1'
            else:
                str_ += '2'
        return str_

    def bfs(self):
        self.graph = self.list2num(self.graph)
        self.eg_arr[0] = self.list2num(self.eg_arr[0])
        self.eg_arr[1] = self.list2num(self.eg_arr[1])

        # 初期条件
        self.dist[self.graph] = 0
        self.que.append(self.graph)

        if self.graph in self.eg_arr:
            return 0

        while self.que:
            g = self.que.popleft()
            if self.dist[g] > self.m: continue

            ng_arr = []
            ind0 = g.rfind('0')
            ind1 = g.rfind('1')
            ind2 = g.rfind('2')
            if ind0 >= 0:
                if (ind1 >= 0 and ind1<ind0) or ind1 < 0:
                    ng = g[:ind0]+'1'+g[ind0+1:]
                    ng_arr.append(ng)
            if ind1 >= 0:
                if (ind0 >= 0 and ind0<ind1) or ind0 < 0:
                    ng = g[:ind1]+'0'+g[ind1+1:]
                    ng_arr.append(ng)
                if (ind2 >= 0 and ind2<ind1) or ind2 < 0:
                    ng = g[:ind1]+'2'+g[ind1+1:]
                    ng_arr.append(ng)
            if ind2 >= 0:
                if (ind1 >= 0 and ind1<ind2) or ind1 < 0:
                    ng = g[:ind2]+'1'+g[ind2+1:]
                    ng_arr.append(ng)

            for ng in ng_arr:
                if ng in self.dist.keys(): continue
                self.dist[ng] = self.dist[g] + 1
                self.que.append(ng)
                if ng in self.eg_arr:
                    return self.dist[ng]
        else:
            return -1


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    io_cnt = 0
    while True:
        try:
            n, m = list(map(int,_in[io_cnt].split(' ')))  # type:list(int)
            graph = []
            for i in range(3):
                _ = list(map(int,_in[io_cnt+i+1].split(' ')))  # type:list(int)
                if _[0] == 0:
                    graph.append([])
                else:
                    graph.append(_[1:])
            io_cnt += 4
            # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
            bfs = BFS(graph,m,n)
            cnt = bfs.bfs()
            # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            print(cnt)
        except:
            break


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    while True:
        n, m = [int(i) for i in input().split()]
        if n == 0 and m == 0:
            return
        _, *a = [int(i) for i in input().split()]
        _, *b = [int(i) for i in input().split()]
        _, *c = [int(i) for i in input().split()]
        a.insert(0, 0)
        b.insert(0, 0)
        c.insert(0, 0)

        q = deque()
        q.appendleft([a, b, c, 0, -1])
        tmp = [i for i in range(0, n+1)]

        while q:
            # d はカウンタ
            a, b, c, d, t = q.pop()
            """
            print(a)
            print(b)
            print(c)
            print('=======')
            """
            # 終了
            if d > m:
                print(-1)
                break
            if a == tmp or c == tmp:
                print(d)
                break
            # a から b
            if a[-1] > b[-1] and t != 1:
                q.appendleft([a[:-1], b+[a[-1]], c[:], d+1, 0])
            # b から a
            if b[-1] > a[-1] and t != 0:
                q.appendleft([a+[b[-1]], b[:-1], c[:], d+1, 1])
            # b から c
            if b[-1] > c[-1] and t != 3:
                q.appendleft([a[:], b[:-1], c+[b[-1]], d+1, 2])
            # c から b
            if c[-1] > b[-1] and t != 2:
                q.appendleft([a[:], b+[c[-1]], c[:-1], d+1, 3])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def resolve():
    def toC(A, B, C):
        if not (A or B):
            return 0
        if C & 1:
            return toC(A>>1, B>>1, C>>1) # Cにある一番小さいコップは考えない
        if B & 1:
            return (toC(C>>1, B>>1, A>>1) # 一度反対側にどかす
            + toC((A|B|C)>>1, 0, 0) # 反対側からそいつらを持ってくる
            + 1) # B -> C
        if A & 1:
            return (toC(A>>1, B>>1, C>>1) # まずすべてCにまとめる
            + 2 * toC((A|B|C)>>1,0,0) # 端から端へ2回移動させる
            + 2) # A -> B -> C

    while True:
        n, m = map(int, input().split())
        cup = [0 for _ in range(3)]
        if n == 0:
            return
        for i in range(3):
            a = list(map(int, input().split()))
            for s in a[1:]:
                cup[i] |= 1 << s-1
        a = min(toC(*cup), toC(*reversed(cup)))
        print(a if a <= m else -1)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

from collections import deque
import copy

def myinput():
    return map(int,readline().split())

def bfs(n,S_start):
    q = deque()
    q.append(S_start)
    count = 0
    while q:
        S = q.popleft()
        state = S[0]
        a = S[0][0]
        b = S[0][1]
        c = S[0][2]
        which = S[1]
        if len(state[0])==(n+1):
            return count 
        elif len(state[2])==(n+1):
            return count
        else:
            if which:
                if a[-1]>b[-1]:
                    state[1].append(state[0].pop())
                    count += 1
                    nS = [state, not which ]
                    q.append(nS)
                else:
                    state[0].append(state[1].pop())
                    count += 1
                    nS = [state, not which ]
                    q.append(nS)
            else:
                if b[-1]>c[-1]:
                    state[2].append(state[1].pop())
                    count += 1
                    nS = [state, not which ]
                    q.append(nS)
                else:
                    state[1].append(state[2].pop())
                    count += 1
                    nS = [state, not which ]
                    q.append(nS)
    return float("inf")
            
ls_ans = []
while True:
    n,m = myinput()
    if (n+m)==0:
        break
    state_start_1 = [ [0] + list(myinput())[1:] for _ in range(3) ]
    state_start_2 = copy.deepcopy(state_start_1)
    S1 = [state_start_1,True]
    S2 = [state_start_2,False]
    ans1 = bfs(n,S1)
    ans2 = bfs(n,S2)
    ans = min(ans1,ans2)
    if ans<=m:
        ls_ans.append(ans)
    else:
        ls_ans.append(-1)

for i in range(len(ls_ans)):
    print(ls_ans[i])

Submission status: Accepted

Solution code:
def move(a,b):
    aa = a[:]
    bb = b[:]
    bb.append(aa.pop(-1))
    return aa,bb

def move_is_True(a,b):
    if len(a) == 0:
        return False
    elif len(b) == 0 or a[-1]>b[-1]:
        return True
    return False

def search(abc_first, n):
    counts = [10**10]
    abcs = [(abc_first, abc_first, 0)]
    while True:
        if len(abcs) == 0 or min(counts) < sorted(abcs, key=lambda x:x[2])[0][2]:
            break
        new_abcs = []
        for abc, last_abc, count in abcs:
            abc_copy = abc[:]
            #print("abc", abc)
            a = abc_copy[0]
            b = abc_copy[1]
            c = abc_copy[2]
            if len(a) == n or len(c) == n:
                counts.append(count)
            else:
                movements = [(a,b), (b,a), (c,b), (b,c)]
                can_move = [move_is_True(a,b) for a,b in movements] #a2b, b2a, c2b, b2c
                #print("can_move", can_move)
                for i in range(4):
                    if can_move[i]:
                        new_count = count+1
                        x,y = movements[i]
                        x,y = move(x,y)
                        if i == 0:
                            new_abc = [x,y,c]
                        elif i == 1:
                            new_abc = [y,x,c]
                        elif i == 2:
                            new_abc = [a,y,x]
                        elif i == 3:
                            new_abc = [a,x,y]
                        #print(abc, new_abc, new_count, n)
                        if new_abc != last_abc:
                            if new_count < 15000000:
                                new_abcs.append((new_abc, abc, new_count))
            abcs = new_abcs[:]
    return min(counts)

n, m = map(int, input().split())
while (m!=0 or n!=0):
    abc = []
    for i in range(3):
        abc.append(list(map(int, input().split()))[1:])
    ans = search(abc, n)
    if ans <= m:
        print(ans)
    else:
        print(-1)
    n, m = map(int, input().split())

Submission status: Accepted

Solution code:
from collections import deque

def main():
    while True:
        n, m = [int(i) for i in input().split()]
        if n == 0 and m == 0:
            return
        _, *a = [int(i) for i in input().split()]
        _, *b = [int(i) for i in input().split()]
        _, *c = [int(i) for i in input().split()]
        a.insert(0, 0)
        b.insert(0, 0)
        c.insert(0, 0)

        q = deque()
        q.appendleft([a, b, c, 0, -1])
        tmp = [i for i in range(0, n+1)]

        while q:
            a, b, c, d, t = q.pop()
            if d > m:
                print(-1)
                break
            if a == tmp or c == tmp:
                print(d)
                break

            if a[-1] > b[-1] and t != 1 and t != 0:
                q.appendleft([a[:-1], b+[a[-1]], c[:], d+1, 0])
            if b[-1] > a[-1] and t != 0 and t != 1:
                q.appendleft([a+[b[-1]], b[:-1], c[:], d+1, 1])
            if b[-1] > c[-1] and t != 3 and t != 2:
                q.appendleft([a[:], b[:-1], c+[b[-1]], d+1, 2])
            if c[-1] > b[-1] and t != 2 and t != 3:
                q.appendleft([a[:], b+[c[-1]], c[:-1], d+1, 3])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    def rec(i):
        if i == 0:
            return 0
        
        tray = cups[n - i]
        if tray == 'A':
            return rec(i - 1)
        elif tray == 'B':
            return 2 * 3 ** (i - 1) - 1 - rec(i - 1)
        else:
            return rec(i - 1) + 2 * 3 ** (i - 1)
    
    while True:
        n, m = map(int, f_i.readline().split())
        if n == 0:
            break
        
        cups = [None] * n
        for tray in 'ABC':
            itr = map(int, f_i.readline().split())
            next(itr)
            for i in itr:
                cups[i-1] = tray
        
        num = rec(n)
        ans = min(num, 3 ** n - 1 - num)
        if ans <= m:
            print(ans)
        else:
            print(-1)

solve()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    while True:
        n, m = [int(i) for i in input().split()]
        if n == 0 and m == 0:
            return
        _, *a = [int(i) for i in input().split()]
        _, *b = [int(i) for i in input().split()]
        _, *c = [int(i) for i in input().split()]
        a.insert(0, 0)
        b.insert(0, 0)
        c.insert(0, 0)

        q = deque()
        q.appendleft([a, b, c, 0, -1])
        tmp = [i for i in range(0, n+1)]

        while q:
            # d はカウンタ
            a, b, c, d, t = q.pop()
            """
            print(a)
            print(b)
            print(c)
            print('=======')
            """
            # 終了
            if d > m:
                print(-1)
                break
            if a == tmp or c == tmp:
                print(d)
                break
            # a から b
            if a[-1] > b[-1] and t != 1 and t != 0:
                q.appendleft([a[:-1], b+[a[-1]], c[:], d+1, 0])
            # b から a
            if b[-1] > a[-1] and t != 0 and t != 1:
                q.appendleft([a+[b[-1]], b[:-1], c[:], d+1, 1])
            # b から c
            if b[-1] > c[-1] and t != 3 and t != 2:
                q.appendleft([a[:], b[:-1], c+[b[-1]], d+1, 2])
            # c から b
            if c[-1] > b[-1] and t != 2 and t != 3:
                q.appendleft([a[:], b+[c[-1]], c[:-1], d+1, 3])


if __name__ == '__main__':
    main()