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: Accepted

Solution code:
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def solve(N, M, A, B, C, ab):
    A = [0] + A
    B = [0] + B
    C = [0] + C
    for i in range(M + 1):
        if len(A) == N + 1 or len(C) == N + 1:
            return i
        if ab:
            if A[-1] < B[-1]:
                A.append(B.pop())
            else:
                B.append(A.pop())
        else:
            if C[-1] < B[-1]:
                C.append(B.pop())
            else:
                B.append(C.pop())
        ab = not ab
    return IINF


while True:
    N, M = list(map(int, sys.stdin.readline().split()))
    if N == M == 0:
        break
    _, *A = list(map(int, sys.stdin.readline().split()))
    _, *B = list(map(int, sys.stdin.readline().split()))
    _, *C = list(map(int, sys.stdin.readline().split()))

    s1 = solve(N, M, A, B, C, True)
    s2 = solve(N, M, A, B, C, False)
    ans = min(s1, s2)
    if ans <= M:
        print(ans)
    else:
        print(-1)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

ans = []
while 1:
	n, m = MAP()
	if n == 0 and m == 0:
		break
	A = LIST()
	B = LIST()
	C = LIST()

	A = A[1:]
	B = B[1:]
	C = C[1:]
	goal = defaultdict(int)
	for i in A:
		goal[n-i] = 0
	for i in B:
		goal[n-i] = 1
	for i in C:
		goal[n-i] = 2
	# print(goal)
	p = 0  # Aにすべての円盤あり
	x = 0
	for i in range(n-1, -1, -1):
		d = abs(p-goal[i])
		x += d*(3**i)
		if d == 1:
			p = 2-p
	tmp = min(x, 3**n-1-x)
	if tmp <= m:
		ans.append(tmp)
	else:
		ans.append(-1)

for i in ans:
	print(i)

Submission status: Runtime Error

Solution code:
def dfs(A, B, C, x):
    key = tuple(A+[0]+B+[0]+C)
    if key in memo or M < x:
        return
    memo[key] = x
    if A:
        if not B or B[-1] < A[-1]:
            B.append(A.pop())
            dfs(A, B, C, x+1)
            A.append(B.pop())
    if B:
        if not A or A[-1] < B[-1]:
            A.append(B.pop())
            dfs(A, B, C, x+1)
            B.append(A.pop())
        if not C or C[-1] < B[-1]:
            C.append(B.pop())
            dfs(A, B, C, x+1)
            B.append(C.pop())
    if C:
        if not B or B[-1] < C[-1]:
            B.append(C.pop())
            dfs(A, B, C, x+1)
            C.append(B.pop())
INF = 10**18
while 1:
    N, M = map(int, input().split())
    if not N:
        break
    _, *A = map(int, input().split())
    _, *B = map(int, input().split())
    _, *C = map(int, input().split())
    memo = {}
    dfs(A, B, C, 0)
    *F, = range(1, N+1)
    res = min(memo.get(tuple([0, 0] + F), INF), memo.get(tuple(F + [0, 0]), INF))
    if res <= M:
        print(res)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
def dfs(A, B, C, x):
    key = tuple(A+[0]+B+[0]+C)
    if key in memo or M < x:
        return
    memo[key] = x
    if A:
        if not B or B[-1] < A[-1]:
            B.append(A.pop())
            dfs(A, B, C, x+1)
            A.append(B.pop())
    if B:
        if not A or A[-1] < B[-1]:
            A.append(B.pop())
            dfs(A, B, C, x+1)
            B.append(A.pop())
        if not C or C[-1] < B[-1]:
            C.append(B.pop())
            dfs(A, B, C, x+1)
            B.append(C.pop())
    if C:
        if not B or B[-1] < C[-1]:
            B.append(C.pop())
            dfs(A, B, C, x+1)
            C.append(B.pop())
INF = 10**18
while 1:
    N, M = map(int, input().split())
    if not N:
        break
    _, *A = map(int, input().split())
    _, *B = map(int, input().split())
    _, *C = map(int, input().split())
    memo = {}
    dfs(A, B, C, 0)
    *F, = range(1, N+1)
    res = min(memo.get(tuple([0, 0] + F), INF), memo.get(tuple(F + [0, 0]), INF))
    if res <= M:
        print(res)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import itertools
R, C = map(int, raw_input().split())
a = []
for i in range(R):
    a.append(map(int, raw_input().split()))

ans = 0
for pat in itertools.product((0, 1), repeat = R):
    rev = [[c^p for c in row]
            for (row, p) in zip(a, pat)]
    cols = zip(*rev)
    zeros = [c.count(0) for c in cols]
    points = [max(z, R-z) for z in zeros]
    ans = max(sum(points), ans)
print ans

# def rev(row):
#     return [1^v for v in row]
# 
# def count(m):
#     rm = zip(*m)
#     return sum([max(rm[c].count(0), rm[c].count(1)) for c in range(C)])
# 
# ans = 0
# for i in range(1 << R):
#     b = [a[r] if (i >> r) & 1 else rev(a[r]) for r in range(R)]
#     ans = max(ans, count(b))
# 
# print ans