Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

虫食い算

足し算は筆算で簡単に計算できますが、もし、いくつかの数字が欠けていたら、欠けている数字を埋めるのは簡単でしょうか？ 例えば、以下のような筆算において、１から９の数字が一度しか現れないという条件があるとき、ＣとＥのマスに入る数字はいくつになるでしょう？ この場合、Ｃに入るのは８，Ｅに入るのは５が正解となります。このように、数字がいくつか欠けている演算を虫食い算と呼びます。

１から９の数字が一度しか現れないという条件はそのままで、以下のようにもっとたくさんの数字が欠けていたら、正解となる数字の埋め方は一通りしかないのでしょうか？ 実は、必ず一通りに決まるとは限りません。

上の図のような形をした虫食い算の、ＡからＩの各マスの情報が与えられたとき、正しい埋め方が何通りあるかを出力するプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

A B C D E F G H I

１行に、虫食い算の Ａ から Ｉ のマスに入っている数字の情報が与えられる。ただし、与えられた値が -1 のときは、そのマスの数字が欠けていることを表す。-1 以外の値は、1 から 9 の整数のいずれかで、それらの間に重複はない。

Output

正しい埋め方が何通りあるかを１行に出力する。

Sample Input 1

7 6 -1 1 -1 9 2 3 4

Sample Output 1

1

Sample Input 2

7 6 5 1 8 9 2 3 4

Sample Output 2

0

Sample Input 3

-1 -1 -1 -1 -1 -1 8 4 6

Sample Output 3

12

Sample Input 4

-1 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output 4

168



Sample input:
7 6 -1 1 -1 9 2 3 4


Sample output:
1

Submission status: Wrong Answer

Solution code:
ls = list(map(int, input().split()))
print(len(ls)*ls.count(-1))

Submission status: Accepted

Solution code:
num=[0]*9
used=[0]*10
def check():
    if num[0]+num[2]+num[5]-num[8]+(num[1]+num[4]-num[7])*10+(num[3]-num[6])*100: return 0
    return 1

def dfs(id):
    if id==9:return check()
    if num[id]!=-1:return dfs(id+1)
    ans=0
    for i in range(1,10):
        if used[i]:continue
        num[id]=i;used[i]=1
        ans+=dfs(id+1)
        num[id]=-1;used[i]=0
    return ans

num=list(map(int,input().split()))
for x in num:
    if x!=-1:used[x]=True
print(dfs(0))

Submission status: Accepted

Solution code:
import itertools
u=[1,2,3,4,5,6,7,8,9]
a=0
n=list(map(int,input().split()))
for x in itertools.permutations(u):
    f=0
    for i in range(9):
        if n[i]!=-1 and n[i]!=x[i]:f=1
    if f:continue
    if x[0]+x[2]+x[5]-x[8]+(x[1]+x[4]-x[7])*10+(x[3]-x[6])*100==0:a+=1
print(a)

Submission status: Accepted

Solution code:
def f(n,x):
    for i in range(9):
        if n[i] != -1 and n[i] != x[i]: return 1
import itertools
u=[1,2,3,4,5,6,7,8,9]
a=0
n=list(map(int,input().split()))
for x in itertools.permutations(u):
    if f(n,x):continue
    if x[0]+x[2]+x[5]-x[8]+(x[1]+x[4]-x[7])*10+(x[3]-x[6])*100==0:a+=1
print(a)

Submission status: Accepted

Solution code:
from collections import deque
*N, = map(int, input().split())
used = set([i for i in N if i != -1])
deq = deque({i for i in range(1, 10)} - used)
C = [1, 10, 1, 100, 10, 1, -100, -10, -1]
def solve():
    res = 0
    for i in range(9):
        res += C[i] * N[i]
    return+(res == 0)

def dfs(c, rest):
    if rest == 0:
        return solve()

    if N[c] != -1:
        return dfs(c+1, rest)

    res = 0
    for i in range(rest):
        v = deq.popleft()
        N[c] = v
        res += dfs(c+1, rest-1)
        deq.append(v)
    N[c] = -1
    return res
print(dfs(0, len(deq)))

Submission status: Accepted

Solution code:
import itertools
a = input().split()
b = set(map(str,range(1,10)))
n, c = [], 0
for i in range(9):
    if a[i] in b:b.remove(a[i])
    else:n.append(i)
for i in itertools.permutations(tuple(b)):
    for j in range(len(n)):a[n[j]] = i[j]
    if int(a[0]) + int(a[1] + a[2]) + int(a[3] + a[4] + a[5]) == int(a[6] + a[7] + a[8]):c += 1
print(c)

Submission status: Accepted

Solution code:
from itertools import permutations as pm

def judge(lst):
  a, b, c, d, e, f, g, h, i = lst
  return a + (b * 10 + c) + (d * 100 + e * 10 + f) == (g * 100 + h * 10 + i)

def solve(lst, rest):
  n = len(rest)
  if n == 0:
    return int(judge(lst))
  ans = 0
  for loc in pm(rest, n):
    tmp = lst[:]
    for i in loc:
      tmp[tmp.index(-1)] = i
    ans += judge(tmp)
  return ans

lst = list(map(int, input().split()))
rest = {i for i in range(1, 10)} - set(lst)
print(solve(lst, rest))

Submission status: Accepted

Solution code:
def make_list(X) :
    if X != -1 :
        x_list = [X]
    else :
        x_list = [i for i in range(1, 10)]
    return x_list

A, B, C, D, E, F, G, H, I = map(int, input().split())
a_list = make_list(A)
b_list = make_list(B)
c_list = make_list(C)
d_list = make_list(D)
e_list = make_list(E)
f_list = make_list(F)
g_list = make_list(G)
h_list = make_list(H)
i_list = make_list(I)

cnt = 0
for a in a_list :
    for b in b_list :
        if b not in [a]:
            for c in c_list :
                if c not in [a, b] :
                    for d in d_list :
                        if d not in [a, b, c] :
                            for e in e_list :
                                if e not in [a, b, c, d] :
                                    for f in f_list :
                                        if f not in [a, b, c, d, e] :
                                            for g in g_list :
                                                if g not in [a, b, c, d, e, f] :
                                                    for h in h_list :
                                                        if h not in [a, b, c, d, e, f, g] :
                                                            for i in i_list :
                                                                if i not in [a, b, c, d, e, f, g, h] :
                                                                    if a+10*b+c+100*d+10*e+f == 100*g+10*h+i :
                                                                        cnt += 1
print(cnt)