0
0 комментариев

Решаю задачу:

По данным числам 1 <= n <= 30 и 1 <= w <= 109 и набору чисел 1<=v1, … vn<=109 найдите минимальное число k, для которого число w можно представить как сумму k чисел из набора {v1 … vn}. Каждое число из набора можно использовать сколь угодно раз. Известно, что в наборе есть единица и что для любой пары чисел из набора одно из них делится на другое. Гарантируется, что в оптимальном ответе число слагаемых не превосходит 104.

Выведите число k и сами слагаемые.

Пример тестовых данных:

4 90 1 2 10 50

Ответ:

5 50 10 10 10 10

Мой вариант:

def solve_sum(num_array, value):
    dividers = [i for i in num_array if i <= value]
    dividers = sorted(dividers, reverse=True)
    res = []
    n = 0
    while value:
        res += [dividers[n]] * (value // dividers[n])
        k = (value // dividers[n])
        value %= dividers[n]
        n += 1
    return str(n)+' '+" ".join(map(str, res))
 
 
results = input().split(' ')
results = [int(i) for i in results]
value = results[1]
num_array = results[2:]
 
print(solve_sum(num_array, value))

Однако, что-то неверно и выдает ошибку:

Failed test #1. Wrong answer
Input:
4 90 1 2 10 50
Your output:
2 50 10 10 10 10
Correct output:
5 50 10 10 10 10

Что не так?


Добавить комментарий