Участник:Andriygav/FP

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/FP

class my_string(str):
    @staticmethod
    def _my_lt(a, b):
        if len(a) > len(b):
            return False
        elif len(a) < len(b):
            return True
        else:
            if a > b:
                return False
            else:
                return True
    @staticmethod
    def _my_gt(a, b):
        if len(a) > len(b):
            return True
        elif len(a) < len(b):
            return False
        else:
            if a > b:
                return True
            else:
                return False
 
    def _max(self, b):
        if self._my_gt(self, b):
            return self
        else:
            return b
 
    def __lt__(self, b):
        ab = self+b
        ba = b+self
        return self._my_lt(ab, ba)
 
    def __gt__(self, b):
        ab = self+b
        ba = b+self
        return self._my_gt(ab, ba)
 
 
def solver(n, k, a):
    a_s = list(map(my_string, a))
    a_s = sorted(a_s, reverse=True)
 
    P = [["0" for _ in range(9)] for _ in range(k)]
 
    a = list(map(int, a_s))
 
    P[0][a[0] % 9] = str(a[0])
 
    for i in range(1, n):
        for j in range(k-1, 0, -1):
            for q in range(9):
                if P[j-1][q] != "0":
                    P[j][(q + a[i]) % 9] = my_string(P[j][(q + a[i]) % 9])._max(my_string(P[j-1][q] + str(a[i])))
 
        if P[0][a[i] % 9] == "0" or my_string(a[i])._my_gt(my_string(a[i]), my_string(P[0][a[i] % 9])):
            P[0][a[i] % 9] = str(a[i])
 
    if P[k-1][0] == '0':
        return '-1'
    else:
        return P[k-1][0]
 
t = int(input())
answers = []
for i in range(t):
    n, k = list(map(int, input().split()))
    a = []
    for j in range(n):
        a.append(int(input()))
    answers.append(solver(n, k, a))
 
for ans in answers:
    print(ans)