Balance beam (1) P18679
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.
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
- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++ Python