Problem:


Score : 1500 points

Problem Statement

The currency used in Takahashi Kingdom is Myon.
There are 1-, 10-, 100-, 1000- and 10000-Myon coins, and so forth. Formally, there are 10^n-Myon coins for any non-negative integer n.

There are N items being sold at Ex Store.
The price of the i-th (1≦i≦N) item is A_i Myon.

Takahashi is going to buy some, at least one, possibly all, of these N items.
He hates receiving change, so he wants to bring coins to the store so that he can pay the total price without receiving change, no matter what items he chooses to buy.
Also, since coins are heavy, he wants to bring as few coins as possible.

Find the minimum number of coins he must bring to the store. It can be assumed that he has an infinite supply of coins.

Constraints

1≦N≦20,000

1≦A_i≦10^{12}

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum number of coins Takahashi must bring to the store, so that he can pay the total price without receiving change, no matter what items he chooses to buy.

Sample Input 1

3
43 24 37

Sample Output 1

16

There are seven possible total prices: 24, 37, 43, 61, 67, 80, and 104.
With seven 1-Myon coins, eight 10-Myon coins and one 100-Myon coin, Takahashi can pay any of these without receiving change.

Sample Input 2

5
49735011221 970534221705 411566391637 760836201000 563515091165

Sample Output 2

105



Sample input:
3
43 24 37


Sample output:
16

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8, i8), cache=True)
def test(A, keta, n):
    # 10^keta の位を n にできるか
    MOD = 10**(keta + 1)
    I = [(n * 10**keta, (n + 1) * 10**keta)]  # [l, r)
    for x in A:
        newI = I.copy()
        x %= MOD
        for l, r in I:
            l, r = l + MOD - x, r + MOD - x
            if l >= MOD:
                l, r = l - MOD, r - MOD
            if r <= MOD:
                newI.append((l, r))
            else:
                newI.append((l, MOD))
                newI.append((0, r - MOD))
        I = newI
        I.sort(key=lambda x: x[1])
        newI = [(0, 0)] * 0
        for x, y in I:
            while newI and newI[-1][1] >= x:  # つなぐ
                x, y = newI[-1][0], y
                newI.pop()
            newI.append((x, y))
        I = newI
    return I[0][0] == 0

def main(A):
    N = len(A)
    ans = 0
    for keta in range(18):
        for x in range(9, -1, -1):
            if test(A, keta, x):
                ans += x
                break
    return ans

A = np.array(read().split(), np.int64)[1:]
print(main(A))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8, i8), cache=True)
def test(A, keta, n):
    # 10^keta の位を n にできるか
    MOD = 10**(keta + 1)
    I = [(n * 10**keta, (n + 1) * 10**keta)]  # [l, r)
    for x in A:
        if I[0][0] == 0:
            return True
        newI = I.copy()
        x %= MOD
        for l, r in I:
            l, r = l + MOD - x, r + MOD - x
            if l >= MOD:
                l, r = l - MOD, r - MOD
            if r <= MOD:
                newI.append((l, r))
            else:
                newI.append((l, MOD))
                newI.append((0, r - MOD))
        I = newI
        I.sort(key=lambda x: x[1])
        newI = [(0, 0)] * 0
        for x, y in I:
            while newI and newI[-1][1] >= x:  # つなぐ
                x, y = min(x, newI[-1][0]), y
                newI.pop()
            newI.append((x, y))
        I = newI
    return I[0][0] == 0

def main(A):
    N = len(A)
    ans = 0
    for keta in range(18):
        for x in range(9, 0, -1):
            if test(A, keta, x):
                ans += x
                break
    return ans

A = np.array(read().split(), np.int64)[1:]
np.random.shuffle(A)
print(main(A))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8, i8), cache=True)
def test(A, keta, n):
    # 10^keta の位を n にできるか
    MOD = 10**(keta + 1)
    I = [(n * 10**keta, (n + 1) * 10**keta)]  # [l, r)
    for x in A:
        if I[0][0] == 0:
            return True
        newI = I.copy()
        x %= MOD
        for l, r in I:
            l, r = l + MOD - x, r + MOD - x
            if l >= MOD:
                l, r = l - MOD, r - MOD
            if r <= MOD:
                newI.append((l, r))
            else:
                newI.append((l, MOD))
                newI.append((0, r - MOD))
        I = newI
        I.sort(key=lambda x: x[1])
        newI = [(0, 0)] * 0
        for x, y in I:
            while newI and newI[-1][1] >= x:  # つなぐ
                x, y = min(x, newI[-1][0]), y
                newI.pop()
            newI.append((x, y))
        I = newI
    return I[0][0] == 0

def main(A):
    N = len(A)
    ans = 0
    for keta in range(18):
        for x in range(9, 0, -1):
            if test(A, keta, x):
                ans += x
                break
    return ans

A = np.array(read().split(), np.int64)[1:]
print(main(A))

Submission status: Time Limit Exceeded

Solution code:
import itertools
L=list()
N=int(input())
A=list(map(int,input().split()))
b=sum(A)
s=len(str(b))
K=[0]*s
for n in range(1,len(A)+1):
    for conb in itertools.combinations(A, n):
        L.append(list(conb))
for i in range((2**N)-1):
  R=L[i]
  a=sum(R)
  t=len(str(a))
  for j in range(t):
    K[j]=max(K[j],(a%(10**(j+1)))//(10**j))
print(sum(K))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8), cache=True)
def solve(A, keta):
    # 10^keta の位を n にできるか
    MOD = 10**(keta + 1)
    B = 10**keta
    nums = [0]
    for x in A:
        x %= MOD
        n = len(nums)
        for i in range(n):
            s = nums[i] + x
            if s >= MOD:
                s -= MOD
            nums.append(s)
        nums.sort()
        # x, y, z とあって、x + z < B ならば、y は捨ててよい
        tmp = []
        for x in nums:
            while len(tmp) >= 2 and tmp[-2] + B > x:
                tmp.pop()
            tmp.append(x)
        nums = tmp
    return nums[-1] // B

def main(A):
    N = len(A)
    ans = 0
    for keta in range(18):
        x = solve(A, keta)
        ans += x
    return ans

A = np.array(read().split(), np.int64)[1:]
np.random.shuffle(A)
print(main(A))