Problem:


パズル

1 〜 9 の数字を 14 個組み合わせて完成させるパズルがあります。与えられた 13 個の数字にもうひとつ数字を付け加えて完成させます。

パズルの完成条件は

同じ数字を２つ組み合わせたものが必ずひとつ必要です。

残りの12 個の数字は、３個の数字の組み合わせ４つです。

３個の数字の組み合わせ方は、同じ数字を３つ組み合わせたものか、または３つの連続する数字を組み合わせたものです。ただし、9 1 2 のような並びは連続する数字とは認められません。

同じ数字は4 回まで使えます。

13 個の数字からなる文字列を読み込んで、パズルを完成することができる数字を昇順に全て出力するプログラムを作成してください。なお、1〜9 のどの数字を付け加えてもパズルを完成させることができないときは 0 を出力してください。

例えば与えられた文字列が 3456666777999 の場合

「2」があれば、　234 567 666 77 999

「3」があれば、　33 456 666 777 999

「5」があれば、　345 567 666 77 999

「8」があれば、　345 666 678 77 999

というふうに、2 3 5 8 のいずれかの数字が付け加えられるとパズルは完成します。「6」でも整いますが、5 回目の使用になるので、この例では使えないことに注意してください。

Input

入力は複数のデータセットからなります。各データセットとして、13 個の数字が１行に与えられます。データセットの数は 50 を超えません。

Output

データセットごとに、パズルを完成させることができる数字を昇順に空白区切りで１行に出力します。

Sample Input

3649596966777
6358665788577
9118992346175
9643871425498
7755542764533
1133557799246

Output for the Sample Input

2 3 5 8
3 4
1 2 3 4 5 6 7 8 9
7 8 9
1 2 3 4 6 7 8
0



Sample input:
3649596966777
6358665788577
9118992346175
9643871425498
7755542764533
1133557799246


Sample output:
2 3 5 8
3 4
1 2 3 4 5 6 7 8 9
7 8 9
1 2 3 4 6 7 8
0

Submission status: Wrong Answer

Solution code:
import sys

def pokakito(num_line):
    if not num_line and flag == 1:
        result_lis.append(check_num)
        return True
    for num in num_line:
        if three(num, num_line): return True
        if two(num, num_line): return True
        if straight(num, num_line): return True
    
def three(num, num_line):
    count = 0
    for check in num_line[:3]:
        if check == num:
            count += 1
    else:
        if count == 3:
            if pokakito(num_line[3:]): return True

def two(num, num_line):
    global flag
    count = 0
    for check in num_line[:2]:
        if check == num:
            count += 1
    else:
        if count == 2:
            flag += 1
            if pokakito(num_line[2:]): return True
            flag -= 1

def straight(num, num_line):
    num_lis = [num,num+1,num+2]
    for i in range(3):
        for check in num_lis:
            if check < 0 or (not check in num_line):
                for i in range(3):
                    num_lis[i] = num_lis[i]-1
                break
        else:
            for n in num_lis:
                index = 0
                while num_line:
                    if num_line[index] == n:
                        del num_line[index]
                        break
                    index += 1
            else:
                if pokakito(num_line): return True
            
flag = 0
result_lis = []
check_num = 0
for input_line in sys.stdin:
    for i in range(9):
        check_num = i+1
        input_line = input_line.rstrip()
        line = sorted(input_line + str(check_num))
        line = ''.join(line)
        index = line.find(str(check_num))
        if line[index:index+5] == str(check_num)*5:
            continue
        pokakito([int(char) for char in line])
        result = sorted([str(num) for num in result_lis])
        flag = 0
    else:
        if result_lis:
            print ' '.join(result)
        else:
            print 0
else:
    flag = 0
    result_lis = []
    check_num = 0

Submission status: Wrong Answer

Solution code:
def Solve(c,s):
    if s:
        for i in range(9):
            if c[i]>4:return False
            elif c[i]>=2:
                cc=c[:]
                cc[i]-=2
                if Solve(cc,False):return True
    else:
        if c.count(0)+c.count(3)==9:return True
        else:
            for i in range(9):
                if c[i]<0:return False
                elif c[i]>=1 and i<7:
                    cc=c[:]
                    for j in range(3):
                        cc[i+j]-=1
                    if Solve(cc,False):return True
_in=""
while True:
    ans=[]
    try:_in=input()
    except EOFError:break
    for i in range(9):
        l=sorted((_in+str(i+1))[::1])
        count=[l.count(str(j+1))for j in range(9)]
        if Solve(count,True):ans.append(str(i+1))
    print(0 if len(ans)==0 else " ".join(ans))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0043

"""
import sys
from sys import stdin
input = stdin.readline


def dfs(hand, count):
    # ??¢??????n????????£??????????????¨????¢??????????
    if count < 1:
        return True

    for i, n in enumerate(hand):
        if n >= 3:
            c_hand = hand[:]
            c_hand[i] -= 3
            res = dfs(c_hand[:], count-1)
            if res:
                return True
        elif n >= 1:
            if i > 7:
                return False
            if hand[i+1] >= 1 and hand[i+2] >= 1:
                c_hand = hand[:]
                c_hand[i] -= 1
                c_hand[i+1] -= 1
                c_hand[i+2] -= 1
                res = dfs(c_hand[:], count-1)
                if res:
                    return True
            else:
                return False
    return True


def solve(data):
    """
    1) ??????1??????????????¨
    2) ??¢??????4??????????????¨
    3) ????????°??????5?????\??????????????¨
    :param data: ??????
    :return: ??????????????????
    """

    ans = []

    # ?????¨?????????l???9??????????????????????????????????????????????????§??????????????????????????????????????§????????°????????????????????°????????????????????????
    for tsumo in range(1, 10):
        my_hand = data[:]
        my_hand.append(tsumo)       #  ????????????????????°??????1????¶????

        remaining = [0] * 10
        for n in my_hand:
            remaining[n] += 1

        if max(remaining) > 4:  #  ?????????3?¢????
            continue

        # ?????????1????¢????
        for i, n in enumerate(remaining[1:], start=1):
            if n >= 2:
                c_remaining = remaining[:]
                c_remaining[i] -= 2
                res = dfs(c_remaining[:], 4)

                if res:
                    ans.append(tsumo)
                    break
    return ans


def main(args):
    #hand = '3649596966777'
    #data = list(map(int, list(hand)))

    for line in sys.stdin:
        data = list(map(int, list(line.strip())))
        result = solve(data)

        if len(result) > 0:
            print(*result)
        else:
            print(0)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
from collections import deque

try:
    while True:
        a = list(sorted(map(int, input())))
        result = []

        for i in range(1, 10):
            if a.count(i) == 4:
                continue

            _a = sorted(a+[i])
            dq = deque([(_a, 0)])
            while dq:
                hand, mentu = dq.popleft()
                if mentu == 5:
                    if not hand:
                        result.append(i)
                        break
                    continue

                if hand.count(hand[0]) >= 2:
                    dq.append((hand[2:], mentu+1))
                if hand.count(hand[0]) >= 3:
                    dq.append((hand[3:], mentu+1))
                if hand.count(hand[0]+1) > 0 and hand.count(hand[0]+2) > 0:
                    _hand = hand[:]
                    del _hand[0]
                    del _hand[_hand.index(hand[0]+1)]
                    del _hand[_hand.index(hand[0]+2)]
                    dq.append((_hand, mentu+1))

        print(" ".join(map(str, result)) if result else 0)


except EOFError as e:
    print(e)
    exit()

Submission status: Wrong Answer

Solution code:
def Judge(P,cnt2=0):
    for i in range(1,11):
        if P[i]==1 or P[i]==4:
            P[i],P[i+1],P[i+2]=0,P[i+1]-1,P[i+2]-1
        elif P[i]==2:
            if cnt2>=1:
                return False
            P[i]-=2
            if Judge(P[:],1):
                return True
            P[i+1]-=2
            P[i+2]-=2
            if Judge(P[:]):
                return True
        elif P[i]==3:
            P[i]-=3
            if Judge(P[:]):
                return True
            P[i+1]-=1
            P[i+2]-=1
            if Judge(P[:]):
                return True
        elif P[i]<0:
            return False
    return True

while True:
    try:
        s=map(int,raw_input())
    except EOFError:
        break
    L=[0]*12
    ans=[]
    for i in s:
        L[i]+=1
    for i in range(1,10):
        L[i]+=1
        if max(L)!=5 and Judge(L[:]):
            ans.append(i)
        L[i]-=1
    print " ".join(map(str,ans)) if len(ans)>0 else 0

Submission status: Wrong Answer

Solution code:
def Judge(P,cnt2=0):
    for i in range(1,11):
        if P[i]==1 or P[i]==4:
            P[i],P[i+1],P[i+2]=0,P[i+1]-1,P[i+2]-1
        elif P[i]==2:
            if cnt2>=1:
                return False
            P[i]-=2
            cnt2=1
            if Judge(P[:],cnt2):
                return True
            P[i+1]-=2
            P[i+2]-=2
            if Judge(P[:],cnt2):
                return True
        elif P[i]==3:
            P[i]-=3
            if Judge(P[:],cnt2):
                return True
            P[i+1]-=1
            P[i+2]-=1
            if Judge(P[:],cnt2):
                return True
        elif P[i]<0:
            return False
    return True

while True:
    try:
        s=map(int,raw_input())
    except EOFError:
        break
    L=[0]*12
    ans=[]
    for i in s:
        L[i]+=1
    for i in range(1,10):
        L[i]+=1
        if max(L)!=5 and Judge(L[:]):
            ans.append(i)
        L[i]-=1
    print " ".join(map(str,ans)) if len(ans)>0 else 0

Submission status: Wrong Answer

Solution code:
def Judge(P,cnt2=0):
    for i in range(1,11):
        if P[i]==1:
            P[i],P[i+1],P[i+2]=0,P[i+1]-1,P[i+2]-1
        elif P[i]==2:
            if cnt2>=1:
                return False
            P[i]-=2
            cnt2=1
            if Judge(P[:],cnt2):
                return True
            P[i+1]-=2
            P[i+2]-=2
            if Judge(P[:],cnt2):
                return True
        elif P[i]==3:
            P[i]-=3
            if Judge(P[:],cnt2):
                return True
            P[i+1]-=1
            P[i+2]-=1
            if Judge(P[:],cnt2):
                return True
        elif P[i]==4:
            P[i],P[i+1],P[i+2]=0,P[i+1]-1,P[i+2]-1
            if Judge(P[:],cnt2):
                return True
            P[i+1],P[i+2]=P[i+1]-3,P[i+2]-3
            if Judge(P[:],cnt2):
                return True
        elif P[i]<0:
            return False
    return True

while True:
    try:
        s=map(int,raw_input())
    except EOFError:
        break
    L=[0]*12
    ans=[]
    for i in s:
        L[i]+=1
    for i in range(1,10):
        L[i]+=1
        if max(L)!=5 and Judge(L[:]):
            ans.append(i)
        L[i]-=1
    print " ".join(map(str,ans)) if len(ans)>0 else 0

Submission status: Wrong Answer

Solution code:
def rm_shuntsu(hand):
	for hai in set(hand):
		if (hai in hand) and (hai+1 in hand) and (hai+2 in hand):
			if len(hand) == 3: return True
			hand1 = hand[:]
			hand1.remove(hai);hand1.remove(hai+1);hand1.remove(hai+2)
			return is_hora(hand1)
	else: return False
		
def rm_kotsu(hand):
	for hai in set(hand):
		if hand.count(hai) >= 3:
			if len(hand) == 3: return True
			hand1 = hand[:]
			hand1.remove(hai);hand1.remove(hai);hand1.remove(hai)
			return is_hora(hand1)
	else: return False
	
def is_hora(hand):
	return rm_shuntsu(hand) or rm_kotsu(hand)
	
while True:
	try:
		hand = map(int, raw_input())
		ans = []
		for tumo in range(1,10):
			hand1 = hand[:]
			hand1.append(tumo)
			for janto in set(hand1):
				if 2 <= hand1.count(janto) <= 4:
					hand2 = hand1[:]
					hand2.remove(janto);hand2.remove(janto)
					if is_hora(hand2):
						ans.append(tumo)
						break
		print " ".join(map(str, sorted(ans))) if len(ans) > 0 else 0
	except:
		break

Submission status: Wrong Answer

Solution code:
from collections import Counter

while 1:
    try:
        puzzle = map(int, raw_input())
    except EOFError:
        break
    ret = []
    for i in xrange(1, 10):
        for j in xrange(1, 10):
            tmp = Counter(puzzle + [i])
            if tmp[j] < 2:
                continue
            tmp[j] -= 2
            for k in xrange(1, 10):
                if not tmp[k]:
                    continue
                if tmp[k] >= 3:
                    tmp[k] -= 3

                while tmp[k] and tmp[k + 1] and tmp[k + 2]:
                    tmp[k] -= 1
                    tmp[k + 1] -= 1
                    tmp[k + 2] -= 1
                if tmp[k]:
                    break
            else:
                ret.append(i)
                break
    if ret:
        print ' '.join(map(str, ret))
    else:
        print 0

Submission status: Time Limit Exceeded

Solution code:
def Solve(c,s):
    if s:
        for i in range(9):
            if c[i]>4:return False
            elif c[i]>=2:
                cc=c[:]
                cc[i]-=2
                if Solve(cc,False):return True
    else:
        if c.count(0)+c.count(3)==9:return True
        else:
            for i in range(9):
                if c[i]<0:return False
                elif c[i]>=1 and i<7:
                    cc=c[:]
                    for j in range(3):
                        cc[i+j]-=1
                    if Solve(cc,False):return True
_in=""
while True:
    ans=[]
    try:_in="9118992346175"
    except EOFError:break
    for i in range(9):
        l=sorted((_in+str(i+1))[::1])
        count=[l.count(str(j+1))for j in range(9)]
        if Solve(count,True):ans.append(str(i+1))
    print(0 if len(ans)==0 else " ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
def Solve(c,s):
    if s:
        if max(c)>4:return False
        for i in range(9):
            if c[i]>=2:
                cc=c[:]
                cc[i]-=2
                if Solve(cc,False):return True
    else:
        check=0
        for i in range(4):check+=c.count(3*i)
        if check==9:return True
        else:
            for i in range(7):
                if c[i]>=1:
                    cc=c[:]
                    for j in range(3):
                        cc[i+j]-=1
                        if cc[i+j]<0:break
                    if Solve(cc,False):return True
_in=""
while True:
    ans=[]
    try:_in="1123345567799"
    except EOFError:break
    for i in range(9):
        l=(_in+str(i+1))[::1]
        count=[l.count(str(j+1))for j in range(9)]
        if Solve(count,True):ans.append(str(i+1))
    print(0 if len(ans)==0 else " ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
def Solve(c,s):
    if s:
        if max(c)>4:return False
        for i in range(9):
            if c[i]>=2:
                cc=c[:]
                cc[i]-=2
                if Solve(cc,False):return True
    else:
        check=0
        for i in range(4):check+=c.count(3*i)
        if check==9:return True
        else:
            for i in range(7):
                if c[i]>=1:
                    cc=c[:]
                    for j in range(3):
                        cc[i+j]-=1
                        if cc[i+j]<0:break
                    if Solve(cc,False):return True
_in=""
while True:
    ans=[]
    try:_in=input()
    except EOFError:break
    for i in range(9):
        l=(_in+str(i+1))[::1]
        count=[l.count(str(j+1))for j in range(9)]
        if Solve(count,True):ans.append(str(i+1))
    print(0 if len(ans)==0 else " ".join(ans))

Submission status: Accepted

Solution code:
def is_solved(nums):
  keys = set(nums)
  for key in keys:
    if nums.count(key) >= 2:
      tmp = nums[:]
      tmp.remove(key)
      tmp.remove(key)
      for key in keys:
        key_count = tmp.count(key)
        if key_count == 4:
          if key + 1 in tmp and key + 2 in tmp:
            for _ in range(4): tmp.remove(key)
            tmp.remove(key + 1)
            tmp.remove(key + 2)
        elif key_count == 3:
          for _ in range(3): tmp.remove(key)

        elif tmp.count(key + 1) >= key_count and tmp.count(key + 2) >= key_count:
          for _ in range(key_count):
            tmp.remove(key)
            tmp.remove(key + 1)
            tmp.remove(key + 2)
      if tmp == []:
        return True
  return False

while True:
  try:
    puzzle = list(map(int, list(input())))
    ans = []
    for i in range(1, 10):
      if puzzle.count(i) <= 3 and is_solved(puzzle + [i]):
        ans.append(i)
    if ans:
      print(*ans)
    else:
      print(0)
  except EOFError:
    break

Submission status: Accepted

Solution code:
from sys import *
from collections import *

def uck(e,y):
  d = Counter(dict(e))
  for i in xrange(1,13):
    if d[i] < 0 or d[i] >= 5: return False
  ab = 0
  for i in xrange(1,10): ab += abs(d[i])
  if ab == 0: return True

  for i in xrange(1,10):
    if d[i] == 0 : continue
    d[i]-=3
    if uck(d,y): return True
    d[i]+=3
    if not y:
      d[i]-=2
      if uck(d,True): return True
      d[i]+=2
    d[i]-=1;d[i+1]-=1;d[i+2]-=1
    if uck(d,y):return True

for s in stdin:
  s = map(int,s[:-1]); v = ""
  for j in xrange(1,10):
    if len(s) == 14: s=s[:-1]
    s.append(j)
    if uck(Counter(sorted(s)),False): v += str(j)+" "
  if v == "": print 0
  else: print v[:-1]

Submission status: Accepted

Solution code:
import sys

def pokakito(num_line):
    if not num_line and flag == 1:
        result_lis.append(check_num)
        return True
    for num in num_line:
        if three(num, num_line): return True
        if two(num, num_line): return True
        if straight(num, num_line): return True
    
def three(num, num_line):
    count = 0
    for check in num_line[:3]:
        if check == num:
            count += 1
    else:
        if count == 3:
            if pokakito(num_line[3:]): return True

def two(num, num_line):
    global flag
    count = 0
    for check in num_line[:2]:
        if check == num:
            count += 1
    else:
        if count == 2:
            flag += 1
            if pokakito(num_line[2:]): return True
            flag -= 1

def straight(num, num_line):
    num_lis = [num,num+1,num+2]
    for i in range(3):
        for check in num_lis:
            if check < 0 or (not check in num_line):
                for i in range(3):
                    num_lis[i] = num_lis[i]-1
                break
        else:
            for n in num_lis:
                index = 0
                while num_line:
                    if num_line[index] == n:
                        del num_line[index]
                        break
                    index += 1
            else:
                if pokakito(num_line): return True
            
flag = 0
result_lis = []
check_num = 0
for input_line in sys.stdin:
    for i in range(9):
        check_num = i+1
        input_line = input_line.rstrip()
        line = sorted(input_line + str(check_num))
        line = ''.join(line)
        index = line.find(str(check_num))
        if line[index:index+5] == str(check_num)*5:
            continue
        pokakito([int(char) for char in line])
        result = sorted([str(num) for num in result_lis])
        flag = 0
    else:
        if result_lis:
            print ' '.join(result)
        else:
            print 0
    flag = 0
    result_lis = []
    check_num = 0

Submission status: Accepted

Solution code:
import sys

def pokakito(num_line):
    if not num_line and flag == 1:
        result_lis.append(check_num)
        return True
    for num in num_line:
        if three(num, num_line): return True
        if two(num, num_line): return True
        if straight(num, num_line): return True
    
def three(num, num_line):
    count = 0
    for check in num_line[:3]:
        if check == num:
            count += 1
    else:
        if count == 3:
            if pokakito(num_line[3:]): return True

def two(num, num_line):
    global flag
    count = 0
    for check in num_line[:2]:
        if check == num:
            count += 1
    else:
        if count == 2:
            flag += 1
            if pokakito(num_line[2:]): return True
            flag -= 1

def straight(num, num_line):
    for check in [num,num+1,num+2]:
        if not check in num_line:
            break
    else:
        for n in [num,num+1,num+2]:
            index = 0
            while num_line:
                if num_line[index] == n:
                    del num_line[index]
                    break
                index += 1
        else:
            if pokakito(num_line): return True
            
flag = 0
result_lis = []
check_num = 0
for input_line in sys.stdin:
    for i in range(9):
        check_num = i+1
        input_line = input_line.rstrip()
        line = sorted(input_line + str(check_num))
        line = ''.join(line)
        index = line.find(str(check_num))
        if line[index:index+5] == str(check_num)*5:
            continue
        pokakito([int(char) for char in line])
        result = sorted([str(num) for num in result_lis])
        flag = 0
    else:
        if result_lis:
            print ' '.join(result)
        else:
            print 0
    flag = 0
    result_lis = []
    check_num = 0

Submission status: Accepted

Solution code:
#memo roiti 899204
def rm_s(h):
    seth=set(h)
    for hai in seth:
        if set([hai,hai+1,hai+2])<=seth:
            if len(h)==3:
                return 1
            h1=h[:]
            for i in range(3):
                h1.remove(hai+i)
            return is_hora(h1)
    else:
        return 0

def rm_k(h):
    for hai in set(h):
        if h.count(hai)>=3:
            if len(h)==3:
                return 1
            h1=h[:]
            for i in range(3):
                h1.remove(hai)
            return is_hora(h1)
    else:
        return 0

def is_hora(h):
    return rm_k(h) or rm_s(h)

while 1:
    try:
        h=map(int,raw_input())
        ans=[]
        for a in range(1,10):
            if h.count(a)<=3:
                h1=h[:]+[a]
                for d in set(h1):
                    if 2<= h1.count(d):
                        h1=h[:]+[a]
                        h1.remove(d)
                        h1.remove(d)
                        if is_hora(h1):
                            ans.append(a)
                            break
        print ' '.join(map(str, sorted(ans))) if len(ans)>0 else 0
    except:
        break

Submission status: Accepted

Solution code:
def ch(data):
    data.sort()
    if max(data.count(i) for i in range(1, 10)) > 4:
        return False
    if len(data) == 2 and data[0] == data[1]:
        return True
    for i in range(1, 10):
        if data.count(i) >= 3:
            tmp = data[:]
            for _ in range(3):
                tmp.remove(i)
            if ch(tmp):
                return True
    for i in range(7):
        if i + 1 in data and i + 2 in data and i + 3 in data:
            tmp = data[:]
            for j in range(3):
                tmp.remove(i + j + 1)
            if ch(tmp):
                return True
    return False

while True:
    try:
        data = list(map(int, input()))
        if not len(data):
            break
    except:
        break
    res = []
    for i in range(1, 10):
        if ch(data + [i]):
            res.append(i)
    print(*res if len(res) else [0])

Submission status: Accepted

Solution code:

def check(nums):
    for i in range(9):
        if(nums[i]>4):return False

    for head in range(9):
        anums=nums[:]
        if(anums[head]<2):continue
        anums[head]-=2

        for i in range(9):
            if(anums[i]>=3):
                anums[i]-=3
            while(anums[i]>0):
                if i>=7:break
                ok=True
                for j in range(i,i+3):
                    if anums[j]<=0:
                        ok=False
                if not ok:
                    break
                for j in range(i,i+3):
                    anums[j]-=1

        if not any(anums):
            return True

    return False


while True:
    st=''
    try:
        st=input()
    except:
       break
    nums=[0 for i in range(9)]
    for c in st:
        nums[int(c)-1]+=1

    anss=[]
    for n in range(0,9):
        nums[n]+=1
        if(check(nums[:])):anss.append(n+1)
        nums[n]-=1

    if(len(anss)==0):anss.append(0)
    print(' '.join(map(str,anss)))

Submission status: Accepted

Solution code:
def is_hora(lst):
    for i in range(1,10):
        if lst[i] >= 2:
            if(is_4chunk(lst,i)): return True
    return False

def is_4chunk(lst,atama):
    searchlist = [0]*10
    for i in range(10):
        searchlist[i] = lst[i]
    searchlist[atama] -= 2
    for i in range(1,8):
        if searchlist[i] < 0: return False
        if searchlist[i] >=3: searchlist[i]-=3
        if searchlist[i] ==1:
            searchlist[i]-=1
            searchlist[i+1]-=1
            searchlist[i+2]-=1
        elif searchlist[i] ==2:
            searchlist[i]-=2
            searchlist[i+1]-=2
            searchlist[i+2]-=2
    return (searchlist[8] == 0 or searchlist[8] == 3) and (searchlist[9] == 0 or searchlist[9] == 3)

while True:
    try:
        instr = input()
        pai = [0]*10
        ans = []
        for i in range(13):
            pai[(int(instr[i]))] += 1
        for i in range(1,10):
            if pai[i] == 4: continue
            pai[i] += 1
            if is_hora(pai): ans.append(i)
            pai[i] -= 1
        if len(ans)!=0:
            print(" ".join(list(map(str,ans))))
        else: print(0)

    except EOFError: break

Submission status: Accepted

Solution code:
def Solve(c,s):
    if s:
        if max(c)>4:return False
        for i in range(9):
            if c[i]>=2:
                cc=c[:]
                cc[i]-=2
                if Solve(cc,False):return True
    else:
        check=0
        for i in range(4):check+=c.count(3*i)
        if check==9:return True
        else:
            for i in range(7):
                if c[i]>=1:
                    cc=c[:]
                    isneg=False
                    for j in range(3):
                        cc[i+j]-=1
                        if cc[i+j]<0:
                            isneg=True
                            break
                    if isneg==False and Solve(cc,False):return True
_in=""
while True:
    ans=[]
    try:_in=input()
    except EOFError:break
    for i in range(9):
        l=(_in+str(i+1))[::1]
        count=[l.count(str(j+1))for j in range(9)]
        if Solve(count,True):ans.append(str(i+1))
    print(0 if len(ans)==0 else " ".join(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0043

"""
import sys
from sys import stdin
input = stdin.readline


def dfs(hand, count):
    # ??¢??????n????????£??????????????¨????¢??????????
    if count < 1:
        return True

    for i, n in enumerate(hand[1:], start=1):
        if n == 0:
            continue
        if n >= 3:
            c_hand = hand[:]
            c_hand[i] -= 3
            res = dfs(c_hand[:], count-1)
            if res:
                return True
        if i > 7:
            return False
        if hand[i+1] >= 1 and hand[i+2] >= 1:
            c_hand = hand[:]
            c_hand[i] -= 1
            c_hand[i+1] -= 1
            c_hand[i+2] -= 1
            res = dfs(c_hand[:], count-1)
            if res:
                return True
        else:
            return False


def solve(data):
    """
    1) ??????1??????????????¨
    2) ??¢??????4??????????????¨
    3) ????????°??????5?????\??????????????¨
    :param data: ??????
    :return: ??????????????????
    """
    ans = []                    #  ???????????????????¨????

    # ?????¨?????????l???9??????????????????????????????????????????????????§??????????????????????????????????????§????????°????????????????????°????????????????????????
    for tsumo in range(1, 10):
        my_hand = data[:]
        my_hand.append(tsumo)       #  ????????????????????°??????1????¶????

        remaining = [0] * 10
        for n in my_hand:
            remaining[n] += 1

        if max(remaining) > 4:  #  ?????????3?¢????
            continue

        # ?????????1????¢????
        for i, atama in enumerate(remaining[1:], start=1):
            if atama >= 2:
                c_remaining = remaining[:]
                c_remaining[i] -= 2
                res = dfs(c_remaining[:], 4)
                if res:
                    ans.append(tsumo)
                    break
    return ans


def main(args):
    #hand = '3649596966777'
    #data = list(map(int, list(hand)))

    for line in sys.stdin:
        data = list(map(int, list(line.strip())))
        result = solve(data)

        if len(result) > 0:
            print(*result)
        else:
            print(0)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def check_set(hand):
    set_list = []
    for i in range(9):
        if hand.count(i + 1) >= 3:
            set_list.append([i + 1, i + 1, i + 1])
        if i + 1 in hand and i + 2 in hand and i + 3 in hand:
            set_list.append([i + 1, i + 2, i + 3])
    return set_list

def check_winning(hand):
    if len(hand) == 2:
        if hand[0] == hand[1]:
            return True
        else:
            return False
    set_tmp_list = check_set(hand)
    if len(set_tmp_list) == 0:
        return False
    for set_tmp in set_tmp_list:
        hand_tmp = hand[:]
        for i in range(3):
            hand_tmp.remove(set_tmp[i])
        res = check_winning(hand_tmp)
        if res:
            break
        else:
            continue
    return res

while True:
    try:
        inp = list(map(int, list(input())))
        ans = []
        for i in range(9):
            if inp.count(i + 1) >= 4:
                continue
            inp_tmp = inp[:]
            inp_tmp.append(i + 1)
            if check_winning(inp_tmp):
                ans.append(i + 1)
        if len(ans) == 0:
            print(0)
        else:
            print(*ans)
    except:
        break

Submission status: Accepted

Solution code:
import sys
def f(c,h=0):
 if 2 in c and sum(c)==2:return 1
 if 5 in c:return 0  # sum(c)==2
 if 4 in c:
     k=c.index(4);c[k]-=3
     if f(c,h+1):return 1
     c[k]+=3
 if 3 in c:
     k=c.index(3);c[k]-=3
     if f(c,h+1):return 1
     c[k]+=3
 for i in range(7):
  if c[i]and c[i+1]and c[i+2]:
      c[i]-=1;c[i+1]-=1;c[i+2]-=1
      if f(c,h+1):return 1
      c[i]+=1;c[i+1]+=1;c[i+2]+=1
n='123456789'
for e in sys.stdin:
 e=list(e)
 a=[i for i in n if f([(e+[i]).count(j)for j in n])]
 if a:print(*a)
 else:print(0)

Submission status: Accepted

Solution code:
import sys
def f(c):
 if sum(c)in c:return 1
 if 5 in c or sum(c)==2:return 0
 if 4 in c:
     k=c.index(4);c[k]-=3
     if f(c):return 1
     c[k]+=3
 if 3 in c:
     k=c.index(3);c[k]-=3
     if f(c):return 1
     c[k]+=3
 for i in range(7):
  if c[i]and c[i+1]and c[i+2]:
      c[i]-=1;c[i+1]-=1;c[i+2]-=1
      if f(c):return 1
      c[i]+=1;c[i+1]+=1;c[i+2]+=1
n='123456789'
for e in sys.stdin:
 e=list(e)
 a=[i for i in n if f([(e+[i]).count(j)for j in n])]
 if a:print(*a)
 else:print(0)

Submission status: Accepted

Solution code:
import sys
def f(c):
 if sum(c)in c:return 1
 if 5 in c:return 0
 if 4 in c:
  k=c.index(4);c[k]-=3
  if f(c):return 1
  c[k]+=3
 if 3 in c:
  k=c.index(3);c[k]-=3
  if f(c):return 1
  c[k]+=3
 for i in range(7):
  if c[i]and c[i+1]and c[i+2]:
   c[i]-=1;c[i+1]-=1;c[i+2]-=1
   if f(c):return 1
   c[i]+=1;c[i+1]+=1;c[i+2]+=1
n='123456789'
for e in sys.stdin:
 e=list(e)
 a=[i for i in n if f([(e+[i]).count(j)for j in n])]
 if a:print(*a)
 else:print(0)