Barra d'equilibris (2) P45300


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • 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
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++