I solve the problem:

According to the given numbers 1 <= n <= 30 and 1 <= w <= 10 9 and a set of numbers 1 <= v 1 , ... v n <= 10 9 find the minimum number k for which the number w can be represented as the sum k numbers from the set {v 1 ... v n }. Each number in the set can be used anytime. It is known that there is a unit in the set and that for any pair of numbers from the set one of them is divided by the other. It is guaranteed that in the optimal answer the number of items does not exceed 10 4 .

Print the number k and the terms themselves.

Sample test data:

 4 90 1 2 10 50

Answer:

 5 50 10 10 10 10

My version:

 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))

However, something is wrong and gives an error:

 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

What's wrong?

  • Probably should be n += k - Edward Izmalkov

2 answers 2

In your cycle

 while value: res += [dividers[n]] * (value // dividers[n]) k = (value // dividers[n]) value %= dividers[n] n += 1

In the second iteration, value becomes zero, and the loop ends. Line n += 1 counts the number of cycles, respectively, it is equal to 2. And you need to count the number of dividers, so it needs to be changed to n += k .

    You have an index, not the number of terms. Minimally, add k=0 before the cycle and k += (value // dividers[n]) and accordingly str(k) at the end instead of str(n) .

    You can consider finding the terms for the sum as a record of the entered number w in the calculus system with variable bases v , then the number of terms is simply the sum of the coefficients before the corresponding bases (how many times the base is repeated in a number):

     #!/usr/bin/env python3 def convert(number, bases): for base in sorted(bases, reverse=True): # O(n log n) digit, number = divmod(number, base) # O(log w) for _ in range(digit): yield base n, w, *v = map(int, input().split()) assert len(v) == n terms = list(convert(w, v)) print(len(terms), *terms)