Barra d'equilibris (2) P45300
Una gimnasta es troba al punt mig d’una barra d’equilibris de longitud m. La gimnasta ha de fer n salts endavant o enrera, cadascun de longitud ℓi, sense sortir-se mai de la barra. Feu un programa que calculi de quantes maneres es pot acabar l’exercici a cada posició. Els salts s’han de fer tots, i en l’ordre donat.
Entrada
L’entrada consisteix en la longitud m, seguida del nombre n, seguit de les longituds ℓ1, …, ℓn dels salts. Suposeu 2 ≤ m ≤ 103, que m és parell, 0 ≤ n ≤ 104, i 1 ≤ ℓi ≤ 100.
Sortida
Suposant que la posició inicial és 0 (per tant, les posicions vàlides estan a [−m/2, m/2]), escriviu en ordre les posicions on es pot acabar, junt amb el nombre de maneres de fer-ho mòdul 108 + 7.
Input
1000 3 100 10 1
Output
-111 1 -109 1 -91 1 -89 1 89 1 91 1 109 1 111 1
Input
40 2 10 10
Output
-20 1 0 2 20 1
Input
1000 0
Output
0 1
Input
10 1 100
Output
Input
30 4 5 1 20 2
Output
-12 1 12 1
Input
6 5 1 1 1 1 1
Output
-3 4 -1 10 1 10 3 4
Input
100 36 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
-36 1 -34 36 -32 630 -30 7140 -28 58905 -26 376992 -24 1947792 -22 8347680 -20 30260340 -18 94143280 -16 54186842 -14 805254 -12 51677616 -10 10789439 -8 96296941 -6 67902175 -4 7871599 -2 97496005 0 75134670 2 97496005 4 7871599 6 67902175 8 96296941 10 10789439 12 51677616 14 805254 16 54186842 18 94143280 20 30260340 22 8347680 24 1947792 26 376992 28 58905 30 7140 32 630 34 36 36 1
- Author
- Salvador Roura
- Language
- Catalan
- Other languages
- English
- Official solutions
- C++
- User solutions
- C++