Ալգորիթմներ և Տվյալների Կառուցվածքներ

Աստիճան կառուցելը

Ենթադրենք, որ ձեզ տրված է n աղյուս, և ցանկանում եք այդ աղյուսներով կառուցել աստիճանաձև կառուցվածք՝ ամեն մի աղյուս դնելով հարակից սյունակների վրա: Քանի որ խոսքը վերաբերում է աստիճանի կառուցմանը, երկու սյունակ նույն բարձրությունը չեն կարող ունենալ, և աջ կողմի սյունակները միշտ պետք է բարձր լինեն ձախ կողմի սյունակներից: Ունենալով այդ n աղյուրները, հարկավոր է պարզել, թե քանի տարբեր եղանակով կարելի է կազմել ճիշտ աստիճանաձև կառուցվածք:

Մուտք

Մուտքի միակ տողում տրված է մեկ ամբողջ թիվ n (5 ≤ n ≤ 500):

Ելք

Ծրագիրը ելքում պետք է տպի, թե քանի տարբեր աստիճանաձև կառուցվածք է հնարավոր ստանալ այդ աղյուսներով:

Օրինակներ

Մուտք
Ելք
5
2
11
11
212
995645335

Բացատրություն

  1. n = 5
      2. ㅤ
      x
      x
      x
      x
      x
      ㅤ
      x
      ㅤ
      x
      ㅤ
      x
      x
      x
 

Constraints

Time limit: 10 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue