задача про монетки

Задача G: Монетки Ваня пришел в магазин, чтобы купить призы за олимпиаду. У Вани есть n номиналов монет. i -й номинал стоит a i рублей, у Вани есть по 2 монеты каждого номинала. Приз стоит k рублей. Поскольку в этом магазине сдачи нет, а переплачивать Ваня не собирается, то ему нужно набрать монет на ровно k рублей. Ваня очень занятой, поэтому поручил эту задачу вам!

Формат входных данных В первой строке находятся 2 целых числа n и k ( 1 ≤ n ≤ 10 , 1 ≤ k ≤ 50 ).

Во второй строке находятся n целых чисел, i -е из которых равно a i ( 1 ≤ a i ≤ 50 ).

Формат результата Если Ваня может набрать монет ровно на k рублей, то в первой строке выведите «Yes» (без кавычек).

Во второй строке выведите количество монет, которые Ваня будет использовать.

В третьей строке выведите список стоимостей монет, которыми расплатится Ваня. Их сумма должна быть равна k .

Если Ваня не может расплатиться, то в первой строке выведите «No» (без кавычек).

Примеры Входные данные 2 5 2 1 Результат работы Yes 3 2 2 1 Входные данные 3 1 2 3 4 Результат работы No

вот мой код (он не работает)


from itertools import combinations

def find_coins(n, k, coin_values):
    for i in range(1, n + 1):
        for combination in combinations(coin_values, i):
            if sum(combination) == k:
                return combination

    return None

n, k = map(int, input().split())
coin_values = list(map(int, input().split()))

result = find_coins(n, k, coin_values)

if result:
    print("Yes")
    print(len(result))
    print(*result)
else:
    print("No")


Ответы (0 шт):