Balance beam (1) P18679


Statement
 

pdf   zip

thehtml

A gymnast is at the midpoint of a balance beam of length m. The gymnast must jump n times forward or backward, never leaving the bar. The i-th jump has length ℓi. Write a program to compute all the positions where the gymnast can finish her exercise. The gymnast cannot skip any jump, nor change the order of the jumps.

Input

Input consist of the length m, the number n, and the lengths ℓ1, …, ℓn. Assume 2 ≤ m ≤ 109, that m is even, 0 ≤ n ≤ 18, and 1 ≤ ℓi ≤ 108.

Output

Assuming that the initial position is 0 (hence, the valid positions belong to [−m/2, m/2]), print all the positions where the gymnast can finish. Every position must occur as many times as combinations of jumps make it possible.

Information about the checker

You can print the solutions to this exercise in any order.

Public test cases
  • Input

    1000 3
    100 10 1
    

    Output

    111
    109
    91
    89
    -89
    -91
    -109
    -111
    
  • Input

    40 2
    10 10
    

    Output

    20
    0
    0
    -20
    
  • Input

    1000 0
    

    Output

    0
    
  • Input

    10 1
    100
    

    Output

    
            
                                
  • Input

    30 4
    5 1 20 2
    

    Output

    -12
    12
    
  • Input

    6 5
    1 1 1 1 1
    

    Output

    3
    1
    3
    1
    1
    -1
    3
    1
    1
    -1
    1
    -1
    -1
    -3
    3
    1
    1
    -1
    1
    -1
    -1
    -3
    1
    -1
    -1
    -3
    -1
    -3
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python