Problem p03128 (python)

Fixed submission:
n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-1 for i in range(n+1)]
dp[0]=0
for i in range(n+1):
    #max_tmp = -float("inf")
    for j in am:
        if i+c[j-1]<=n:
            dp[i+c[j-1]] = max(dp[i+c[j-1]], dp[i]+1)
#print(dp)
tmp_n = n
ans =""
for i in range(dp[n]):
    for j in range(m):
        if i==dp[n]-1 and tmp_n- c[am[j]-1] != 0:
            continue
        if tmp_n - c[am[j]-1] >= 0 and dp[tmp_n - c[am[j]-1]] == dp[tmp_n] -1:
            ans+=(str(am[j]))
            tmp_n -= c[am[j]-1]
            break


print(ans)

Buggy submission (verdict: Runtime Error):
n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [0 for i in range(n+1)]

for i in range(n+1):
    max_tmp = -float("inf")
    for j in am:
        if i-c[j-1]>=0:
            max_tmp = max(dp[i-c[j-1]]+1, max_tmp)
    dp[i] = max(dp[i],max_tmp)


flag = True
result = 0
tmp_n = n
x = 0
y = x
while flag==True:
    if tmp_n-c[am[x]-1] >= 0 and dp[tmp_n-c[am[x]-1]] == dp[tmp_n] - 1:
        result = result * 10 + am[x]
        tmp_n = tmp_n-c[am[x]-1]
        x = 0
    elif tmp_n-c[am[x]-1]<0:
        x = x + 1
        if x == len(am):
            one = result%10
            result = int((result-one)/10)
            tmp_n +=c[one-1]
            x = am.index(one)+1

    elif x < len(am)-1:
         x+=1

    if tmp_n==0:
        break


print(result)

Buggy submission (verdict: Runtime Error):
n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [0 for i in range(n+1)]

for i in range(n+1):
    max_tmp = -float("inf")
    for j in am:
        if i-c[j-1]>=0:
            max_tmp = max(dp[i-c[j-1]]+1, max_tmp)
    dp[i] = max(dp[i],max_tmp)



flag = True
result = 0
tmp_n = n
x = 0
y = x
while flag==True:

    if tmp_n-c[am[x]-1] >= 0 and dp[tmp_n-c[am[x]-1]] == dp[tmp_n] - 1:
        result = result * 10 + am[x]
        tmp_n = tmp_n-c[am[x]-1]
        x = 0
    elif tmp_n-c[am[x]-1]<0:
        x = x + 1
        if x == len(am):
            one = result%10
            result = int((result-one)/10)
            tmp_n +=c[one-1]
            x = am.index(one)+1

    elif x < len(am):
         x+=1

    if tmp_n==0:
        break


print(result)

Buggy submission (verdict: Runtime Error):
pair = [[1, 2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
n, m = [int(x) for x in input().split()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x - 1] for x in given], reverse=True)

dp = (1 + n) * [0]
for i in range(n + 1):
    max_dp = 0
    if i == 0:
        dp[i] = 0
    for j in range(m):
        if i - given_pair[j][1] >= 0:
            if dp[i - given_pair[j][1]] + 1 >= max_dp:
                max_dp = dp[i - given_pair[j][1]] + 1
    dp[i] = max_dp




def choice_list(x, index):
#    print("now_index", index)
#    print(given_pair[x][1])
#    print("now_dp_atai", dp[index - given_pair[x][1]])
    if dp[index - given_pair[x][1]] == dp[index] - 1 and index -given_pair[x][1]>=0:
        if dp[index - given_pair[x][1]] == 0:
            for j in given_pair:
                if index == j[1]:
                    return str(j[0])
            return ""
        else:
            return str(given_pair[x][0]) + choice_list(x, index - given_pair[x][1])

    else:
        return choice_list(x + 1, index)


print(choice_list(0, n))

Buggy submission (verdict: Runtime Error):
pair = [[1, 2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
n, m = [int(x) for x in input().split()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x - 1] for x in given], reverse=True)

dp = (1 + n) * [0]
max_dp = 0
for i in range(n + 1):
    if i == 0:
        dp[i] = 0
    for j in range(m):
        if i - given_pair[j][1] >= 0:
            if dp[i - given_pair[j][1]] + 1 >= max_dp:
                max_dp = dp[i - given_pair[j][1]] + 1
    dp[i] = max_dp




def choice_list(x, index):
#    print("now_index", index)
#    print(given_pair[x][1])
#    print("now_dp_atai", dp[index - given_pair[x][1]])
    if dp[index - given_pair[x][1]] == dp[index] - 1 and index -given_pair[x][1]>=0:
        if dp[index - given_pair[x][1]] == 0:
            for j in given_pair:
                if index == j[1]:
                    return str(j[0])
            return ""
        else:
            return str(given_pair[x][0]) + choice_list(x, index - given_pair[x][1])

    else:
        return choice_list(x + 1, index)


print(choice_list(0, n))

Buggy submission (verdict: Runtime Error):
pair = [[1, 2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
n, m = [int(x) for x in input().split()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x - 1] for x in given], reverse=True)

dp = (1 + n) * [0]
max_dp = 0
for i in range(n + 1):
    if i == 0:
        dp[i] = 0
    for j in range(m):
        if i - given_pair[j][1] >= 0:
            if dp[i - given_pair[j][1]] + 1 >= max_dp:
                max_dp = dp[i - given_pair[j][1]] + 1
    dp[i] = max_dp




def choice_list(x, index):
#    print("now_index", index)
#    print(given_pair[x][1])
#    print("now_dp_atai", dp[index - given_pair[x][1]])
    if dp[index - given_pair[x][1]] == dp[index] - 1:
        if dp[index - given_pair[x][1]] == 0:
            for j in given_pair:
                if index == j[1]:
                    return str(j[0])
            return ""
        else:
            return str(given_pair[x][0]) + choice_list(x, index - given_pair[x][1])

    else:
        return choice_list(x + 1, index)


print(choice_list(0, n))

Buggy submission (verdict: Runtime Error):
pair = [[1, 2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
n, m = [int(x) for x in input().split()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x - 1] for x in given], reverse=True)

dp = (1 + n) * [0]
max_dp = 0
for i in range(n + 1):
    if i == 0:
        dp[i] = 0
    for j in range(m):
        if i - given_pair[j][1] >= 0:
            if dp[i - given_pair[j][1]] + 1 >= max_dp:
                max_dp = dp[i - given_pair[j][1]] + 1
    dp[i] = max_dp




def choice_list(x, index):
#    print("now_index", index)
#    print(given_pair[x][1])
#    print("now_dp_atai", dp[index - given_pair[x][1]])
    if dp[index - given_pair[x][1]] == dp[index] - 1:
        if dp[index - given_pair[x][1]] == 0:
            for j in given_pair:
                if index == j[1]:
                    return str(j[0])
            return ""
        elif index - given_pair[x][1] < 0:
            return "-1"
        else:
            return str(given_pair[x][0]) + choice_list(x, index - given_pair[x][1])

    else:
        return choice_list(x + 1, index)


print(choice_list(0, n))

Buggy submission (verdict: Runtime Error):
pair = [[1, 2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
n, m = [int(x) for x in input().split()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x - 1] for x in given], reverse=True)

dp = (1 + n) * [0]
max_dp = 0
for i in range(n + 1):
    if i == 0:
        dp[i] = 0
    for j in range(m):
        if i - given_pair[j][1] >= 0:
            if dp[i - given_pair[j][1]] + 1 >= max_dp:
                max_dp = dp[i - given_pair[j][1]] + 1
    dp[i] = max_dp

print(given_pair)

print(dp)


def choice_list(x, index):
#    print("now_index", index)
#    print(given_pair[x][1])
#    print("now_dp_atai", dp[index - given_pair[x][1]])
    if dp[index - given_pair[x][1]] == dp[index] - 1:
        if dp[index - given_pair[x][1]] == 0:
            for j in given_pair:
                if index == j[1]:
                    return str(j[0])
            return ""
        elif index - given_pair[x][1] < 0:
            return "-1"
        else:
            return str(given_pair[x][0]) + choice_list(x, index - given_pair[x][1])

    else:
        return choice_list(x + 1, index)


print(choice_list(0, n))

Buggy submission (verdict: Runtime Error):
pair = [[1, 2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
n, m = [int(x) for x in input().split()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x - 1] for x in given], reverse=True)

dp = (1 + n) * [0]
max_dp = 0
for i in range(n + 1):
    if i == 0:
        dp[i] = 0
    for j in range(m):
        if i - given_pair[j][1] >= 0:
            if dp[i - given_pair[j][1]] + 1 >= max_dp:
                max_dp = dp[i - given_pair[j][1]] + 1
    dp[i] = max_dp



def choice_list(x, index):
#    print("now_index", index)
#    print(given_pair[x][1])
#    print("now_dp_atai", dp[index - given_pair[x][1]])
    if dp[index - given_pair[x][1]] == dp[index] - 1:
        if dp[index - given_pair[x][1]] == 0:
            for j in given_pair:
                print(j)
                if index == j[1]:
                    return str(j[0])
            return ""
        elif index - given_pair[x][1] < 0:
            return "-1"
        else:
            return str(given_pair[x][0]) + choice_list(x, index - given_pair[x][1])

    else:
        return choice_list(x + 1, index)


print(choice_list(0, n))

Buggy submission (verdict: Runtime Error):
pair = [[1, 2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
n, m = [int(x) for x in input().split()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x - 1] for x in given], reverse=True)

dp = (1 + n) * [0]
max_dp = 0
for i in range(n + 1):
    if i == 0:
        dp[i] = 0
    for j in range(m):
        if i - given_pair[j][1] >= 0:
            if dp[i - given_pair[j][1]] + 1 >= max_dp:
                max_dp = dp[i - given_pair[j][1]] + 1
    dp[i] = max_dp

print(given_pair)

print(dp)


def choice_list(x, index):
#    print("now_index", index)
#    print(given_pair[x][1])
#    print("now_dp_atai", dp[index - given_pair[x][1]])
    if dp[index - given_pair[x][1]] == dp[index] - 1:
        if dp[index - given_pair[x][1]] == 0:
            for j in given_pair:
                print(j)
                if index == j[1]:
                    return str(j[0])
            return ""
        elif index - given_pair[x][1] < 0:
            return "-1"
        else:
            return str(given_pair[x][0]) + choice_list(x, index - given_pair[x][1])

    else:
        return choice_list(x + 1, index)


print(choice_list(0, n))

Buggy submission (verdict: Runtime Error):
pair = [[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
n,m =[int(x) for x in input().split()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x-1] for x in given],key = lambda x :x[1])
def rec(n,t_list,pair_list):
  if n==0:
    return t_list
  elif n< pair_list[0][1]:
    return t_list[:-1]
  else:
    a = rec(n-pair_list[0][1],t_list+[pair_list[0][0]],pair_list)
    if pair_list[1:]!=[]:
        b = rec(n,t_list,pair_list[1:])
        if len(a)>len(b):
                return a
        elif len(a)==len(b):
                if(a[-1]>=b[-1]):
                        return a
                else:
                        return b
        else:
                return b
    else:
        return a

kotae = map(str,sorted(rec(n,[],given_pair),reverse=True))
print("".join(kotae))

Buggy submission (verdict: Runtime Error):
pair = [[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
n,m =[int(x) for x in input().split()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x-1] for x in given],key = lambda x :x[1])
def rec(n,t_list,pair_list):
  if n==0:
    return t_list
  elif n< pair_list[0][1]:
    return t_list[:-1]
  else:
    a = rec(n-pair_list[0][1],t_list+[pair_list[0][0]],pair_list)
    if pair_list[1:]!=[]:
        b = rec(n,t_list,pair_list[1:])
        if len(a)>len(b):
                return a
        elif len(a)==len(b):
                if(a[-1]>b[-1]):
                        return a
                else:
                        return b
        else:
                return b
    else:
        return a

kotae = map(str,sorted(rec(n,[],given_pair),reverse=True))
print("".join(kotae))

Buggy submission (verdict: Runtime Error):
pair = [[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
n,m =[int(x) for x in input().split()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x-1] for x in given],key = lambda x :x[1])
def rec(n,t_list,pair_list):
  if n==0:
    return t_list
  elif n< pair_list[0][1]:
    return t_list[:-1]
  else:
    a = rec(n-pair_list[0][1],t_list+[pair_list[0][0]],pair_list)
    if pair_list[1:]!=[]:
        b = rec(n,t_list,pair_list[1:])
        if len(a)>=len(b):
                return a
        else:
                return b
    else:
        return a

kotae = map(str,sorted(rec(n,[],given_pair),reverse=True))
print("".join(kotae))

Buggy submission (verdict: Runtime Error):
n,m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(n)]

s=[]
for t in e:
  b_list=0
  for x in t[1:]:
    b_list = b_list | pow(2,x-1)
  s.append(b_list)
result=pow(2,30)-1
for i in s:
   result = result & i
cnt=0
for i in range(30):
  if result & pow(2,i):
    cnt+=1
print(cnt)