Pujant i baixant P61152


Statement
 

pdf   zip

thehtml

Feu un programa que compti el nombre de maneres d’anar des de (0, 0) fins a (n, 0) fent només passos unitaris cap a la dreta, ja siguin horitzontals, en diagonal cap amunt, o en diagonal cap avall. A més, en cap moment es pot passar per sota del nivell del terra.

Per exemple, per a n = 3 hi ha quatre solucions:

unit=0.8cm (20,3) linecolor=white [fillstyle=vlines,hatchcolor=green,hatchsep=3pt](0.5,0.5)(4.5,1) [fillstyle=vlines,hatchcolor=green,hatchsep=3pt](5.5,0.5)(9.5,1) [fillstyle=vlines,hatchcolor=green,hatchsep=3pt](10.5,0.5)(14.5,1) [fillstyle=vlines,hatchcolor=green,hatchsep=3pt](15.5,0.5)(19.5,1) linestyle=solid linecolor=black -(1,1)(2,2) -(2,2)(3,2) -(3,2)(4,1) [fillstyle=solid,fillcolor=black](1,1)0.1 [fillstyle=solid,fillcolor=black](2,2)0.1 [fillstyle=solid,fillcolor=black](3,2)0.1 [fillstyle=solid,fillcolor=black](4,1)0.1 -(6,1)(7,2) -(7,2)(8,1) -(8,1)(9,1) [fillstyle=solid,fillcolor=black](6,1)0.1 [fillstyle=solid,fillcolor=black](7,2)0.1 [fillstyle=solid,fillcolor=black](8,1)0.1 [fillstyle=solid,fillcolor=black](9,1)0.1 -(11,1)(12,1) -(12,1)(13,2) -(13,2)(14,1) [fillstyle=solid,fillcolor=black](11,1)0.1 [fillstyle=solid,fillcolor=black](12,1)0.1 [fillstyle=solid,fillcolor=black](13,2)0.1 [fillstyle=solid,fillcolor=black](14,1)0.1 -(16,1)(17,1) -(17,1)(18,1) -(18,1)(19,1) [fillstyle=solid,fillcolor=black](16,1)0.1 [fillstyle=solid,fillcolor=black](17,1)0.1 [fillstyle=solid,fillcolor=black](18,1)0.1 [fillstyle=solid,fillcolor=black](19,1)0.1

Entrada

L’entrada consisteix en diversos casos, cadascun amb una n entre 0 i 2000.

Sortida

Per a cada cas, escriviu el nombre de camins vàlids mòdul 108 + 7.

Public test cases

  • Input

    0
1
2
3
4
5
21
2000

    Output

    1
1
2
4
9
21
42547552
61201932
    • Information
    Author
    Enric Rodríguez
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++