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

Solution code:
import sys
def p(c,l,b):
 for i in l:c[i]+=[-1,1][b]
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]:
   p(c,[i,i+1,i+2],0)
   if f(c):return 1
   p(c,[i,i+1,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 g(c,i):
 a=[0]*9
 for j in e+[i]:a[j-1]+=1
 return a
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
for e in sys.stdin:
 e=list(map(int,e.strip()))
 a=[i for i in range(1,10)if f(g(e,i))]
 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:
 c=[list(e).count(j)for j in n]
 a=[]
 for i in range(9):
  t=c[:];t[i]+=1
  if f(t):a+=[i+1]
 if a:print(*a)
 else:print(0)

Submission status: Accepted

Solution code:
def check(nums):
    #print(nums)
    #5回以上出てこないか判別
    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):
                #8以上が1になってても成立しないからFalse
                if i>=7:
                    break
                ok=True
                for j in range(i,i+3):
                    if anums[j]<=0:
                        ok=False
                #okがFalseなら順番になってない
                if not ok:
                    break
                #okがTrueなら順番になっているので一ずつ減らす。
                for j in range(i,i+3):
                    anums[j]-=1
        #全て0になっていればTrue
        if not any(anums):
            return True
    return False

while True:
    st=""
    try:
        st=input()
    except:
        break
        #9個の配列を作り0を入れる
    nums=[0 for i in range(9)]
    #各数字の数を数える
    for c in st:
        nums[int(c)-1]+=1
    #答えの配列を作る
    anss=[]
    #与えられたものに1~9を一つずつ加えてそれぞれで判定
    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:
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
                elif mentu > 5:
                    continue

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

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


except EOFError:
    exit()

Submission status: Accepted

Solution code:
import sys

def dfs(hands, pair):
    hands.sort()

    if not hands:
        return True
    target = hands[0]
    # sequence
    if all(map(lambda x: x in hands, range(target, target + 3))):
        for i in range(target, target + 3):
            hands.remove(i)
        if dfs(hands, pair):
            return True
        for i in range(target, target + 3):
            hands.append(i)
    # triple
    if hands.count(target) >= 3:
        for i in range(3):
            hands.remove(target)
        if dfs(hands, pair):
            return True
        for i in range(3):
            hands.append(target)
    # pair
    if not pair and hands.count(target) >= 2:
        for i in range(2):
            hands.remove(target)
        if dfs(hands, True):
            return True
        for i in range(2):
            hands.append(target)
    return False

for line in filter(lambda line: line.strip(), sys.stdin.readlines()):
    result = []
    data = [int(ch) for ch in line.strip()]
    for num in filter(lambda x: data.count(x) < 4, range(1, 10)):
        data_cp = list(data)
        data_cp.append(num)
        data_cp.sort()
        if dfs(data_cp, False):
            result.append(num)
    if result:
        print " ".join(map(str, result))
    else:
        print 0

Submission status: Accepted

Solution code:
import sys
for line in sys.stdin.readlines():
    li=[0]*10
    for i in map(int,line.strip()):
        li[i]+=1
    ans=[]
    for addnum in [i for i in xrange(1,10) if not li[i]>=4]:
        t_li=li[:]
        t_li[addnum]+=1
        for remnum in [i for i in xrange(1,10) if t_li[i]>=2]:
            t2_li=t_li[:]
            t2_li[remnum]-=2
            top=1
            while (not -1 in t2_li) and top<=7:
                if t2_li[top]==0:
                    top+=1
                elif t2_li[top]>=3:
                    t2_li[top]-=3
                else:
                    for i in xrange(3):
                        t2_li[top+i]-=1
            if top==8 and (t2_li[8]==0 or t2_li[8]==3) and (t2_li[9]==0 or t2_li[9]==3):
                ans.append(addnum)
                break
    if ans==[]:print 0
    else:print " ".join(map(str,ans))
#temp

Submission status: Accepted

Solution code:
def main():
    while True:
        try:
            n = [int(x) for x in raw_input()]
            n.sort()
            solve(n)
        except EOFError as e:
            break

def solve(input_numbers):
    valid_numbers = []
    c = count_number(input_numbers);
    for i in range(9):
        if c[i] == 4:
            continue
        c[i] += 1
        if isvalid(c, 0, False):
            valid_numbers.append(i+1)
        c[i] -= 1

    s = " ".join(map(str, valid_numbers)) if len(valid_numbers) > 0 else "0"
    print(s)

def count_number(input_numbers):
    c = [0] * 9
    for i in input_numbers:
        c[i-1] += 1
    return c

def isvalid(input_numbers, pos, head):
    if pos == 8:
        if head and input_numbers[8] == 0:
            return True
        elif head and input_numbers[8] == 3:
            return True
        elif (not head) and input_numbers[8] == 2:
            return True
        else:
            return False

    if input_numbers[pos] == 0:
        return isvalid(input_numbers, pos+1, head)

    if input_numbers[pos] == 1:
        if not can_sequence(input_numbers, pos, 1):
            return False
        else:
            input_numbers[pos] -= 1
            input_numbers[pos+1] -= 1
            input_numbers[pos+2] -= 1
            r = isvalid(input_numbers, pos+1, head)
            input_numbers[pos] += 1
            input_numbers[pos+1] += 1
            input_numbers[pos+2] += 1
            return r

    if input_numbers[pos] == 2:
        if not head:
            input_numbers[pos] -= 2
            r = isvalid(input_numbers, pos+1, True)
            input_numbers[pos] += 2
            if r:
                return True

        if can_sequence(input_numbers, pos, 2):
            input_numbers[pos] -= 2
            input_numbers[pos+1] -= 2
            input_numbers[pos+2] -= 2
            r = isvalid(input_numbers, pos+1, head)
            input_numbers[pos] += 2
            input_numbers[pos+1] += 2
            input_numbers[pos+2] += 2
            return r

    if input_numbers[pos] == 3:
        input_numbers[pos] -= 3
        r = isvalid(input_numbers, pos+1, head)
        input_numbers[pos] += 3
        if r:
            return True

        if can_sequence(input_numbers, pos, 1):
            input_numbers[pos] -= 2
            r = isvalid(input_numbers, pos, True)
            input_numbers[pos] += 2
            return r
        else:
            return False

    if input_numbers[pos] == 4:
        input_numbers[pos] -= 3
        r = isvalid(input_numbers, pos, head)
        input_numbers[pos] += 3
        if r:
            return True

        if not head:
            input_numbers[pos] -= 2
            r = isvalid(input_numbers, pos, True)
            input_numbers[pos] += 2
            return r
        else:
            return False

def can_sequence(input_numbers, pos, num):
    if pos > 6:
        return False
    return input_numbers[pos] >= num and input_numbers[pos+1] >= num and input_numbers[pos+2] >= num

main()

Submission status: Accepted

Solution code:

import sys


DEBUG = False


def solv(nums):
    r = []
    for i in range(1, 10):
        if DEBUG:
            print 'i:     ', i
        if judge(list(nums), i):
            r.append(i)
        if DEBUG:
            print '===='
    if len(r) == 0:
        r.append(0)
    return r


def judge(nums, n):
    if nums.count(n) >= 4:
        return False
    else:
        nums.append(n)
        nums.sort()
        heads = overlup(nums)
        r = []
        for h in heads:
            if DEBUG:
                print 'nums:  ', nums
            nums2 = list(nums)
            nums2.pop(nums2.index(h))
            nums2.pop(nums2.index(h))
            if DEBUG:
                print 'head:  ', h
                print 'nums2: ', nums2
            if judge2(nums2):
                r.append(h)
        if r:
            return True
        else:
            return False


def judge2(nums):
    if not nums:
        if DEBUG:
            print '---'
        return True
    nums2 = list(nums)
    h3 = []
    h3.append(nums.pop(0))
    try:
        j = nums.index(h3[0] + 1)
        h3.append(nums.pop(j))
        k = nums.index(h3[0] + 2)
        h3.append(nums.pop(k))
        if DEBUG:
            print h3
        if judge2(nums):
            return True
    except ValueError:
        for i in range(1, len(h3)):
            nums.append(h3.pop(i))
        nums.sort()
        
    h3 = []
    h3.append(nums2.pop(0))
    h3.append(nums2.pop(0))
    if h3[0] == h3[1]:
        h3.append(nums2.pop(0))
        if DEBUG:
            print h3
        if h3[1] == h3[2]:
            return judge2(nums2)
        else:
            return False
    else:
        return False




def overlup(lis):
    r = []
    def func(x, y):
        if x == y and x not in r:
            r.append(x)
        return y
    reduce(func, lis)
    return r


def difference(lis):
    return [y - x for x, y in zip(lis, lis[1:])]


c = 0

for line in sys.stdin:
    c += 1
    if DEBUG:
        print 'CASE:', str(c)
    numbers = map(int, line.rstrip('\n'))
    print ' '.join(map(str, solv(numbers)))

Submission status: Accepted

Solution code:
def Judge(P):
    for h in range(1,10):
        if P[h]>=2:
            H=P[:]
            H[h]-=2
            flag=True
            for i in range(1,10):
                while H[i]%3:
                    for j in range(3):
                        H[i+j]-=1
                        if H[i+j]<0:
                            flag=False
            if flag:
                return True
    return False

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def solve(L):
    m = min(L)
    cnt = L.count(m)

    if cnt > 4:
        return False
    for _ in xrange(cnt):
        L.remove(m)
    if cnt in (1, 4):
        if not L.count(m+1) or not L.count(m+2):
            return False
        L.remove(m+1)
        L.remove(m+2)
    elif cnt == 2:
        if L.count(m+1) < 2 or L.count(m+2) < 2:
            return False
        L.remove(m+1)
        L.remove(m+1)
        L.remove(m+2)
        L.remove(m+2)
    return True if not len(L) else solve(L)

for line in stdin:
    data = [int(s) for s in line.strip()]
    data.append(0)
    answers = []

    for i in xrange(1, 10):
        data[-1] = i
        if data.count(i) > 4:
            continue
        for pair in xrange(1, 10):
            if data.count(pair) < 2:
                continue
            L = data[:]
            L.remove(pair)
            L.remove(pair)
            if solve(L):
                answers.append(str(i))
                break
    print(' '.join(answers) if answers else '0')

Submission status: Accepted

Solution code:
NUM="0123456789"

def atama(x):
    return [e for e in set(x) if x.count(e)>=2]

def koutu(x,i):
    return x.count(i)>=3

def shuntu(x,i):
    return i<8 and x.count(i)>0 and x.count(i+1)>0 and x.count(i+2)>0

def make(x):
    return [int(c) for c in x]

def check(x):
    for e in set(x):
        if koutu(x,e):
            y = [NUM[e]*3]
            x1=x+[]
            x1.remove(e)
            x1.remove(e)
            x1.remove(e)
            if len(x1)==0: return y
            else:
                y1 = check(x1)
                if len(y1)>0: return y+y1
        elif shuntu(x,e):
            x1=x+[]
            y = [NUM[e:e+3]]
            x1.remove(e)
            x1.remove(e+1)
            x1.remove(e+2)
            if len(x1)==0: return y
            else:
                y1 = check(x1)
                if len(y1)>0: return y+y1
    return ""

try:
    while True:
        s = raw_input()
        y = []
        for e in NUM[1:]:
            if s.count(e)>=4: continue
            x = make(s+e)
            for e0 in atama(x):
                s0= [ NUM[e0]*2]
                x1 = x+[]
                x1.remove(e0)
                x1.remove(e0)
                s0 += check(x1)
                if len(s0)==5:
                    y.append(e)
                    break
        if len(y)==0: print 0
        else:
            for e in y:
                print e,
            print
except:
    pass

Submission status: Accepted

Solution code:
def check(x,j=1):
    if sum(x)==0: return True
    for i in range(j,10):
        y = x[:]
        if y[i]>=3:
            y[i] -= 3
            if check(y,i): return True
        y = x[:]
        if i<8 and y[i]>0 and y[i+1]>0 and y[i+2]>0:
            y[i] -= 1
            y[i+1] -= 1
            y[i+2] -= 1
            if check(y,i): return True
    return False

while True:
    c = [0]*10
    try:
        for e in map(int,raw_input()):
            c[e] += 1
    except:
        break

    f = False
    for i in range(1,10):
        c1=c[:]
        if c1[i]>=4: continue
        else: c1[i]+=1
        atama = [j for j,e in enumerate(c1) if e>=2]
        for e in atama:
            c1[e]-=2
            if check(c1):
                f = True
                print i,
                break
            c1[e]+=2
    if f: print
    else: print 0

Submission status: Accepted

Solution code:
def check(x,j=1):
    if sum(x)==0: return True
    for i in range(j,10):
        if x[i]>0:break
    y = x[:]
    if y[i]>=3:
        y[i] -= 3
        if check(y,i): return True
    y = x[:]
    if i<8 and y[i]>0 and y[i+1]>0 and y[i+2]>0:
        y[i] -= 1
        y[i+1] -= 1
        y[i+2] -= 1
        if check(y,i): return True
    return False

while True:
    c = [0]*10
    try:
        for e in map(int,raw_input()):
            c[e] += 1
    except:
        break

    f = False
    for i in range(1,10):
        c1=c[:]
        if c1[i]>=4: continue
        else: c1[i]+=1
        atama = [j for j,e in enumerate(c1) if e>=2]
        for e in atama:
            c1[e]-=2
            if check(c1):
                f = True
                print i,
                break
            c1[e]+=2
    if f: print
    else: print 0

Submission status: Accepted

Solution code:
import sys
def check(x,j=1):
    if sum(x)==0: return 1
    i = j
    while x[i]==0: i+=1
    y = x[:]
    if y[i]>=3:
        y[i] -= 3
        if check(y,i): return 1
    y = x[:]
    if i<8 and y[i]>0 and y[i+1]>0 and y[i+2]>0:
        y[i] -= 1
        y[i+1] -= 1
        y[i+2] -= 1
        if check(y,i): return 1
    return 0
 
for s in sys.stdin:
    c = [0]*10
    for e in map(int,s[:-1]): c[e] += 1
 
    f = 0
    R = range(1,10)
    for i in R:
        c1=c[:]
        if c1[i]>=4:continue
        c1[i]+=1
        for j in R:
            if c1[j]<2:continue
            c1[j]-=2
            if check(c1):
                f = 1
                print i,
                break
            c1[j]+=2
    if f: print
    else: print 0

Submission status: Accepted

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):
			if hand.count(tumo) <= 3:
				for janto in set(hand+[tumo]):
					if 2 <= (hand+[tumo]).count(janto):
						hand1 = hand[:]+[tumo]
						hand1.remove(janto);hand1.remove(janto)
						if is_hora(hand1):
							ans.append(tumo)
							break
		print " ".join(map(str, sorted(ans))) if len(ans) > 0 else 0
	except:
		break

Submission status: Accepted

Solution code:
def rm_s(h):
	for hai in set(h):
		if (hai in h) and (hai+1 in h) and (hai+2 in h):
			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_s(h) or rm_k(h)
	
while True:
	try:
		h = map(int, raw_input())
		ans = []
		for add in range(1,10):
			if h.count(add) <= 3:
				h1 = h[:]+[add]
				for d in set(h1):
					if 2 <= h1.count(d):
						h1 = h[:]+[add]
						h1.remove(d);h1.remove(d)
						if is_hora(h1):
							ans.append(add)
							break
		print " ".join(map(str, sorted(ans))) if len(ans) > 0 else 0
	except:
		break

Submission status: Accepted

Solution code:
def rm_s(h):
	for hai in set(h):
		if (hai in h) and (hai+1 in h) and (hai+2 in h):
			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 True:
	try:
		h = map(int, raw_input())
		ans = []
		for add in range(1,10):
			if h.count(add) <= 3:
				h1 = h[:]+[add]
				for d in set(h1):
					if 2 <= h1.count(d):
						h1 = h[:]+[add]
						h1.remove(d);h1.remove(d)
						if is_hora(h1):
							ans.append(add)
							break
		print " ".join(map(str, sorted(ans))) if len(ans) > 0 else 0
	except:
		break

Submission status: Accepted

Solution code:
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 True:
	try:
		h = map(int, raw_input())
		ans = []
		for add in range(1,10):
			if h.count(add) <= 3:
				h1 = h[:]+[add]
				for d in set(h1):
					if 2 <= h1.count(d):
						h1 = h[:]+[add]
						h1.remove(d);h1.remove(d)
						if is_hora(h1):
							ans.append(add)
							break
		print " ".join(map(str, sorted(ans))) if len(ans) > 0 else 0
	except:
		break

Submission status: Accepted

Solution code:
def f(a):
    if a == [0] * 10:
        return True

    for i in range(1, 10):
        if a[i] < 3: continue
        b = list(a)
        b[i] -= 3
        if f(b):
            return True

    for i in range(3, 10):
        if a[i - 2] == 0 or a[i - 1] == 0 or a[i] == 0: continue
        b = list(a)
        for j in range(i - 2, i + 1):
            b[j] -= 1
        if f(b):
            return True
    return False

try:
    while True:
        a = [0] * 10
        for c in raw_input():
            a[int(c)] += 1
        d = []
        for i in range(1, 10):
            if a[i] == 4: continue
            b = list(a)
            b[i] += 1
            for j in range(1, 10):
                if b[j] < 2: continue
                c = list(b)
                c[j] -= 2
                if f(c):
                    d.append(str(i))
                    break
        print ' '.join(d) if d else 0
except EOFError:
    pass

Submission status: Accepted

Solution code:
from collections import Counter

while 1:
    try:
        puzzle = map(int, raw_input())
    except EOFError:
        break
    ret = []
    for i in xrange(1, 10):
        cnt = Counter(puzzle + [i])
        if cnt[i] > 4:
            continue
        for j in xrange(1, 10):
            if cnt[j] < 2:
                continue
            tmp = Counter(puzzle + [i])
            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: Accepted

Solution code:
import sys
readlines = sys.stdin.readlines
write = sys.stdout.write
memo = {}
def solve(s):
    d = [0]*10
    for c in s:
        d[int(c)] += 1
    def dfs(i, d):
        if i == 10:
            return True
        key = tuple(d)
        if s in key:
            return memo[key]
        if d[i] == 0:
            return dfs(i+1, d)
        if d[i] >= 3:
            d[i] -= 3
            r = dfs(i, d)
            d[i] += 3
            if r:
                memo[key] = True
                return True
        if i+2 <= 9 and d[i+1] >= 1 and d[i+2] >= 1:
            d[i] -= 1; d[i+1] -= 1; d[i+2] -= 1
            r = dfs(i, d)
            d[i] += 1; d[i+1] += 1; d[i+2] += 1
            if r:
                memo[key] = True
                return True
        memo[key] = False
        return False
    ans = []
    for k in range(1, 10):
        if d[k] == 4:
            continue
        d[k] += 1
        for i in range(10):
            if d[i] >= 2:
                d[i] -= 2
                r = dfs(0, d)
                d[i] += 2
                if r:
                    ans.append(k)
                    break
        d[k] -= 1
    if not ans:
        ans.append(0)
    return ans

for line in readlines():
    res = solve(line.strip())
    write(" ".join(map(str, res)))
    write("\n")

Submission status: Accepted

Solution code:
from collections import Counter
from copy import copy

def _check(pi):
    pi=sorted(pi)
    if len(pi)==0:
        return True
    retval=False
    try:
        _pi=copy(pi)
        tmp=_pi[0]
        for i in range(3):
            _pi.remove(tmp)
        retval = retval or _check(_pi)
    except:
        pass

    try:
        _pi=copy(pi)
        tmp=_pi[0]
        for i in range(3):
            _pi.remove(tmp+i)
        retval = retval or _check(_pi)
    except:
        pass

    return retval

def check(pi,tsumo):
    pi=pi+[tsumo]
    c=Counter(pi)
    for i in range(1,10):
        if c[i]>4:
            return False

    for i in range(1,10):
        if c[i]>=2:
            _pi = copy(pi)
            _pi.remove(i)
            _pi.remove(i)
            _pi=sorted(_pi)
            if _check(_pi):
                return True
    return False


while True:
    try:
        s=input()
        s=[int(i) for i in s]
        retval=[]
        for i in range(1,10):
            if check(s,i):
                retval.append(str(i))
        if len(retval)==0:
            print("0")
        else:
            print(" ".join(retval))
    except EOFError:
        break

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=True
                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()
        if st=="":break
    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:
from itertools import combinations_with_replacement, combinations

def gen_dict(nums):
    r = {}
    for i in nums:
        if i in r.keys():
            r[i] += 1
        else:
            r[i] = 1
    return r

def has_more_4(num_dict):
    for i in num_dict.values():
        if i > 4: return True
    return False

def gen_conseq3(nums):
    r = []
    for i in range(1, 8):
        for j in range(i, i+3):
            if j not in nums: break
        else:
            r.append((i, i+1, i+2))
    return r

def gen_same(n, num_dict):
    r = []
    for i, v in num_dict.items():
        if v >= n: r.append(i)
    return r

def gen_prec(c1s, c2s, c3):
    r = []
    for i in c1s:
        for j in i:
            r.append(j)
    for i in c2s:
        for j in range(3): r.append(i)
    for j in range(2):
        r.append(c3)
    return sorted(r)

while True:
    try: line = input()
    except EOFError: break
    
    founds = []
    for i in range(1, 10):
        ln = line + str(i)
        nums = sorted(list(map(int, ln[:])))
        num_dict = gen_dict(nums)
        if has_more_4(num_dict):
            continue
        conseq_3s = gen_conseq3(nums)
        same_3s = gen_same(3, num_dict)
        same_2s = gen_same(2, num_dict)
        was_found = False
        for r in range(1, 5):
            if was_found: break
            for c1s in combinations_with_replacement(conseq_3s, r):
                if was_found: break
                for c2s in combinations(same_3s, 4-r):
                    if was_found: break
                    for c3 in same_2s:
                        pred = gen_prec(c1s, c2s, c3)
                        if pred == nums:
                            founds.append(str(i))
                            was_found = True
    if founds:
        print(' '.join(founds))
    else:
        print(0)

Submission status: Runtime Error

Solution code:
import scala.io.StdIn.{readLine,readInt}

object Main extends App {
  val seq1 = for(i<-1 to 9) yield Vector(i,i,i)
  val seq2 = for(i<-1 to 7) yield Vector(i,i+1,i+2)

  def check(m:Vector[Int], count:Int,u:Int,v:Int):Boolean =
    if(m.length != count) false
    else if(count==2) m(0)==m(1)
    else
      (u to 8).exists( i=> check(m diff seq1(i),count-3,i+1,v)) || (v to 6).exists(i=> check(m diff seq2(i),count-3,u,i))

  Iterator.continually(readLine).takeWhile ( _!=null ).foreach { line =>
    val l = line.map(_.asDigit).toVector
    val m = (1 to 9).filter { i=> l.count( _==i ) < 4 && check((i+:l).sorted,14,0,0) }
    if(m.length>0) println(m.mkString(" ")) else println(0)
  }
}

Submission status: Runtime Error

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])]
 print(*a if a else 0)

Submission status: Runtime Error

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.strip())
 a=[i for i in n if f([(e+[i]).count(j)for j in n])]
 print(*a if a else 0)