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

Գույներով ներկել

Դուք ցանկանում եք ներկել մի գիծ 3 գույներով՝ red, blue և orange: Դուք որոշել եք, որ յուրաքանչյուր մաս ներկելու եք միայն մեկ գույնով։ Որպեսզի գիծը լինի ավելի աչքի ընկնող, որոշել եք հետևել մի քանի կանոնների.
  1. Չի թույլատրվում նույն գույնով ներկել հաջորդական հատվածներ։
  1. blue գույնը միշտ պետք է լինի երկու տարբեր գույների՝ red-ի և orange-ի (կամ orange-ի և red-ի) միջև։
Քանի՞ տարբեր գունավորում կարելի է ստանալ, եթե ամբողջ գիծը բաղկացած է n մասից։

Մուտք

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

Ելք

Ծրագիրը պետք է տպի ստացվող տարբեր գունավորումների քանակը։ Քանի որ պատասխանը կարող է շատ մեծ լինել, անհրաժեշտ է տպել պատասխանի -ի վրա բաժանելիս ստացվող մնացորդը։

Օրինակներ

Մուտք
Ելք
1
2
2
2
3
4

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

  1. (red), (orange)
  1. (red, orange), (orange, red)
  1. (orange, red, orange), (red, blue, orange), (orange, blue, red), (red, orange, red)
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

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