Equal sums (2) P82660


Statement
 

pdf   zip

thehtml

Write a program that, given an integer number s and n integer numbers x1, …, xn, prints the subset (maybe with repeated numbers, but using every xi at most once) lexicographically largest among those whose sum is s.

Input

Input consists of an integer number s, followed by a number n > 0, followed by x1, …, xn.

Output

Print, with the elements sorted non-increasingly, the subset that is greatest in lexicographical order among those that can be made up with x1, …, xn and whose sum is s. If there is none, print “no solution”.

Hint

Sort the given numbers.

Public test cases
  • Input

    6
    7
    1 6 0 1 3 2 0
    

    Output

    {6,0,0}
    
  • Input

    -5
    3
    6 -10 4
    

    Output

    no solution
    
  • Input

    -5
    9
    3 1 -1 -1 0 -3 0 -2 2
    

    Output

    {2,0,0,-1,-1,-2,-3}
    
  • Input

    -9
    3
    -5 6 -4
    

    Output

    {-4,-5}
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++