Problem:


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

Problem B
Quality of Check Digits

The small city where you live plans to introduce a new social security number (SSN) system. Each citizen will be identified by a five-digit SSN. Its first four digits indicate the basic ID number (0000 - 9999) and the last one digit is a check digit for detecting errors.

For computing check digits, the city has decided to use an operation table. An operation table is a 10 $\times$ 10 table of decimal digits whose diagonal elements are all 0. Below are two example operation tables.

Operation Table 1

    

Operation Table 2

    

Using an operation table, the check digit $e$ for a four-digit basic ID number $abcd$ is computed by using the following formula. Here, $i \otimes
 j$ denotes the table element at row $i$ and column $j$.

$e = (((0 \otimes a) \otimes  b) \otimes c) \otimes d$

For example, by using Operation Table 1 the check digit $e$ for a basic ID number $abcd = $ 2016 is computed in the following way.

$e = (((0 \otimes 2) \otimes 0) \otimes 1) \otimes 6$

$\;\;\;  = (( \;\;\;\;\;\;\;\;\;  1 \otimes 0) \otimes 1) \otimes 6$

$\;\;\;  = ( \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; 7 \otimes 1) \otimes 6$

$\;\;\;  =  \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; 9 \otimes 6$

$\;\;\;  =  \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;  6$

Thus, the SSN is 20166.

Note that the check digit depends on the operation table used. With Operation Table 2, we have $e = $ 3 for the same basic ID number 2016, and the whole SSN will be 20163.

Figure B.1. Two kinds of common human errors

The purpose of adding the check digit is to detect human errors in writing/typing SSNs. The following check function can detect certain human errors. For a five-digit number $abcde$, the check function is defined as follows.

check($abcde$) $ = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e$

This function returns 0 for a correct SSN. This is because every diagonal element in an operation table is 0 and for a correct SSN we have $e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$:

check($abcde$) $ = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e = e \otimes e = 0$

On the other hand, a non-zero value returned by check indicates that the given number cannot be a correct SSN. Note that, depending on the operation table used, check function may return 0 for an incorrect SSN. Kinds of errors detected depends on the operation table used; the table decides the quality of error detection.

The city authority wants to detect two kinds of common human errors on digit sequences: altering one single digit and transposing two adjacent digits, as shown in Figure B.1. 

An operation table is good if it can detect all the common errors of the two kinds on all SSNs made from four-digit basic ID numbers 0000{9999. Note that errors with the check digit, as well as with four basic ID digits, should be detected. For example, Operation Table 1 is good. Operation Table 2 is not good because, for 20613, which is a number obtained by transposing the 3rd and the 4th digits of a correct SSN 20163, check(20613) is 0. Actually, among 10000 basic ID numbers, Operation Table 2 cannot detect one or more common errors for as many as 3439 basic ID numbers.

Given an operation table, decide how good it is by counting the number of basic ID numbers for which the given table cannot detect one or more common errors.

Input

The input consists of a single test case of the following format.

$x_{00}$ $x_{01}$ ... $x_{09}$

...

$x_{90}$ $x_{91}$ ... $x_{99}$

The input describes an operation table with $x_{ij}$ being the decimal digit at row $i$ and column $j$. Each line corresponds to a row of the table, in which elements are separated by a single space. The diagonal elements $x_{ii}$ ($i = 0, ... , 9$) are always 0.

Output

Output the number of basic ID numbers for which the given table cannot detect one or more common human errors.

Sample Input 1

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

Sample Output 1

0

Sample Input 2

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

Sample Output 2

3439

Sample Input 3

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

Sample Output 3

9995

Sample Input 4

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Sample Output 4

10000



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


Sample output:
0

Submission status: Wrong Answer

Solution code:
import copy
T = [[int(x) for  x in input().split()] for i in range(10)]

def E(ID):
    if len(ID)!=4:
        print(len(ID))
    ret = 0
    for d in ID:
        d  =int(d)
        ret = T[ret][d]
    return ret

def solve(ID):
    e = E(ID)
    for i in range(4):
        for j in range(10):
            kari = copy.deepcopy(ID)
            if kari[i] == str(j):
                continue
            kari[i] = str(j)
            if E(kari) == e:
 #               print(kari,ID)
                return 1
    for i in range(3):
        kari = copy.deepcopy(ID)
        if kari[i] == kari[i+1]:
            continue
        kari[i],kari[i+1] =kari[i+1],kari[i]
        if E(kari) == e:
#            print(kari,ID)
            return 1
    if E(ID[:3]+[str(e)]) == int(ID[3]) and int(ID[3])!=e:

        return 1

    return 0
ans = 0
for i in range(10000):
    ID  =[j for j in str(i)]
    ID = ['0']*(4-len(ID)) + ID
    ans += solve(ID)

print(ans)

Submission status: Wrong Answer

Solution code:
matrix = [[0 for _ in xrange(10)] for _ in xrange(10)]
for i in xrange(10):
    matrix[i] = map(int, raw_input().split())


def checkDigit(n):
    xor = matrix[0][int(n[0])]

    for i in xrange(1, len(n)):
        a = int(n[i])
        xor = matrix[xor][a]
    return xor


ans = 0
for num in xrange(10000):
    n = "%04d" % num
    master = checkDigit(n)
    n += str(master)
    c = False
    hit = False
    for i in xrange(len(n) - 1):
        if n[i] != n[i + 1]:
            c = True
            l = n[:i] + n[i + 1] + n[i] + n[i + 2:]
            if 0 == checkDigit(l):
                hit = True
                break

    if hit:
        ans += 1
print ans

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        a = [LI() for _ in range(10)]
        sm = {}
        for i in range(10**4):
            c = 0
            t = 10**3
            while t > 0:
                k = i // t % 10
                c = a[c][k]
                t //= 10
            sm[i] = c
        e = collections.defaultdict(set)
        for i in range(10):
            for j in range(10):
                for k in range(10):
                    for l in range(10):
                        t = i * 1000 + j * 100 + k * 10 + l
                        for m in range(10):
                            if i != m:
                                u = m * 1000 + j * 100 + k * 10 + l
                                e[t].add(u)
                            if j != m:
                                u = i * 1000 + m * 100 + k * 10 + l
                                e[t].add(u)
                            if k != m:
                                u = i * 1000 + j * 100 + m * 10 + l
                                e[t].add(u)
                            if l != m:
                                u = i * 1000 + j * 100 + k * 10 + m
                                e[t].add(u)
                            if i != j:
                                u = j * 1000 + i * 100 + k * 10 + l
                                e[t].add(u)
                            if j != k:
                                u = i * 1000 + k * 100 + j * 10 + l
                                e[t].add(u)
                            if k != l:
                                u = i * 1000 + j * 100 + l * 10 + k
                                e[t].add(u)

        r = 0
        for i in range(10**4):
            t = sm[i]
            if i % 10 != t and sm[i - i % 10 + t] == i % 10:
                r += 1
                continue
            for k in e[i]:
                if sm[k] == t:
                    r += 1
                    break
        rr.append(r)


        break



    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
import copy
T = [[int(x) for  x in input().split()] for i in range(10)]

def E(ID):
#    if len(ID)!=4:
    #    print(len(ID))
    ret = 0
    for d in ID:
        d  =int(d)
        ret = T[ret][d]
    return ret

def solve(ID):
    e = E(ID)
    for i in range(4):
        for j in range(10):
            kari = copy.deepcopy(ID)
            if kari[i] == str(j):
                continue
            kari[i] = str(j)
            if T[E(kari)][e]==0:
                return 1
    for i in range(10):
        if T[E(ID)][i] == 0 and i!=e:
            return 1
    for i in range(3):
        kari = copy.deepcopy(ID)
        if kari[i] == kari[i+1]:
            continue
        kari[i],kari[i+1] =kari[i+1],kari[i]
        if T[E(kari)][e]==0:
            return 1
    if T[E(ID[:3]+[str(e)])][int(ID[3])]==0 and int(ID[3])!=e:

        return 1
    #print(ID ,e)
    return 0
ans = 0
for i in range(10000):
    ID  =[j for j in str(i)]
    ID = ['0']*(4-len(ID)) + ID
    ans += solve(ID)

print(ans)

Submission status: Accepted

Solution code:
matrix = [[0 for _ in xrange(10)] for _ in xrange(10)]
for i in xrange(10):
    matrix[i] = map(int, raw_input().split())


def checkDigit(n):
    xor = matrix[0][int(n[0])]

    for i in xrange(1, len(n)):
        a = int(n[i])
        xor = matrix[xor][a]
    return xor


def check(n):
    for i in xrange(len(n)):
        for j in xrange(10):
            q = str(j)
            if n[i] == q:
                continue
            k = n[:i] + q + n[i + 1:]
            if 0 == checkDigit(k):
                return True

    for i in xrange(len(n) - 1):
        if n[i] != n[i + 1]:
            l = n[:i] + n[i + 1] + n[i] + n[i + 2:]
            if 0 == checkDigit(l):
                return True
    return False


ans = 0
for num in xrange(10000):
    n = "%04d" % num
    master = checkDigit(n)
    n += str(master)
    c = False
    hit = check(n)

    if hit:
        ans += 1
print ans

Submission status: Accepted

Solution code:
from itertools import product
T = [list(map(int, input().split())) for i in range(10)]

def calc(v):
    val = 0
    for e in v:
        val = T[val][e]
    return val

ans = 0
for code in product(range(10), repeat=4):
    e = calc(code)
    ok = 1
    code = list(code) + [e]
    for i in range(5):
        d = code[:]
        for j in range(10):
            if code[i] == j:
                continue
            d[i] = j
            if calc(d) == 0:
                ok = 0
    for i in range(4):
        d = code[:]
        if d[i] == d[i+1]:
            continue
        d[i], d[i+1] = d[i+1], d[i]
        if calc(d) == 0:
            ok = 0
    if ok == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        a = [LI() for _ in range(10)]
        sm = {}
        for i in range(10**4):
            c = 0
            t = 10**3
            while t > 0:
                k = i // t % 10
                c = a[c][k]
                t //= 10
            sm[i] = c
        e = collections.defaultdict(set)
        for i in range(10):
            for j in range(10):
                for k in range(10):
                    for l in range(10):
                        t = i * 1000 + j * 100 + k * 10 + l
                        for m in range(10):
                            if i != m:
                                u = m * 1000 + j * 100 + k * 10 + l
                                e[t].add(u)
                            if j != m:
                                u = i * 1000 + m * 100 + k * 10 + l
                                e[t].add(u)
                            if k != m:
                                u = i * 1000 + j * 100 + m * 10 + l
                                e[t].add(u)
                            if l != m:
                                u = i * 1000 + j * 100 + k * 10 + m
                                e[t].add(u)
                            if i != j:
                                u = j * 1000 + i * 100 + k * 10 + l
                                e[t].add(u)
                            if j != k:
                                u = i * 1000 + k * 100 + j * 10 + l
                                e[t].add(u)
                            if k != l:
                                u = i * 1000 + j * 100 + l * 10 + k
                                e[t].add(u)

        r = 0
        for i in range(10**4):
            t = sm[i]
            if i % 10 != t and a[sm[i - i % 10 + t]][i % 10] == 0:
                r += 1
                continue
            f = False
            for m in range(10):
                if m == t:
                    continue
                if a[t][m] == 0:
                    f = True
                    r += 1
                    break
            if f:
                continue
            for k in e[i]:
                if a[sm[k]][t] == 0:
                    r += 1
                    break
        rr.append(r)


        break



    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
def check(n):
    global x

    check_digit = x[x[x[x[0][n[0]]][n[1]]][n[2]]][n[3]]
    if x[check_digit][n[4]] == 0:
        return True
    else:
        return False

x = [list(map(int, input().split())) for _ in range(10)]

ans = 0

for i in range(10000):
    s = str(i).zfill(4)
    n = list(map(int, s))

    check_digit = x[x[x[x[0][n[0]]][n[1]]][n[2]]][n[3]]
    n.append(check_digit)

    is_break = False
    
    for j in range(5):
        for k in range(10):
            if n[j] == k:
                continue
            temp = n[:]
            temp[j] = k
            if check(temp):
                ans += 1
                is_break = True
                break
        if is_break:
            break

    if is_break:
        continue
        
    for j in range(4):
        if n[j] == n[j + 1]:
            continue
        temp = n[:]
        temp[j], temp[j + 1] = temp[j + 1], temp[j]
        if check(temp):
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
import copy
T = [[int(x) for  x in input().split()] for i in range(10)]

def E(ID):
#    if len(ID)!=4:
    #    print(len(ID))
    ret = 0
    for d in ID:
        d  =int(d)
        ret = T[ret][d]
    return ret

def solve(ID):
    e = E(ID)
    for i in range(4):
        for j in range(10):
            kari = copy.deepcopy(ID)
            if kari[i] == str(j):
                continue
            kari[i] = str(j)
            if T[E(kari)][e]==0:
                return 1
    for i in range(10):
        if T[E(ID)][i] == 0 and i!=e:
            return 1
    for i in range(3):
        kari = copy.deepcopy(ID)
        if kari[i] == kari[i+1]:
            continue
        kari[i],kari[i+1] =kari[i+1],kari[i]
        if T[E(kari)][e]==0:
            return 1
    if T[E(ID[:3]+[str(e)])][int(ID[3])]==0 and int(ID[3])!=e:
        return 1
    #print(ID ,e)
    return 0
ans = 0
for i in range(10000):
    ID  =[j for j in str(i)]
    ID = ['0']*(4-len(ID)) + ID
    ans += solve(ID)

print(ans)