Ovi este un băieţel foarte isteţ căruia îi place să scrie pe asfalt cu creta şi să ţopăie. El desenează cu cretă roşie un dreptunghi de lăţime exact 2 metri şi lungime N metri, pe care îl împarte în pătrate egale de latură 1 metru, unele laturi interioare fiind desenate cu cretă roşie, iar restul laturilor interioare cu cretă albă. Ovi porneşte din pătratul aflat în colţul stânga sus al dreptunghiului, sărind dintr-un pătrat în altul vecin pe linie sau coloană, cu condiţia ca latura care desparte cele două pătrate să nu fie colorată în roşu. El îşi doreşte ca prin sărituri succesive să ajungă în toate pătratele dreptunghiului, dar a observat că numai pentru anumite variante de colorare a laturilor pătratelor reuşeşte acest lucru.
Cerinţă
Ajutaţi-l pe Ovi să numere câte posibilităţi de colorare în roşu a unor laturi interioare ale pătratelor sunt astfel încât plecând din colţul stânga sus să poată ajunge prin sărituri în oricare alt pătrat.

Date de intrare
În fişierul patrate.in se află un singur număr natural N ce reprezintă lungimea în metri a dreptunghiului.

Date de ieşire
În fişierul patrate.out veţi scrie un singur număr natural (urmat de caracterul de sfârşit de linie) ce reprezintă numărul de posibilităţi cerut.

Restricţii şi precizări
• 2 <= N <= 1000

Intrebarea este una matematica
De ce relatia de recurenta pentru numarul de posibilitati de colorare in rosu este:

[Citat] De ce relatia de recurenta pentru numarul de posibilitati de colorare in rosu este:

Indicaţie: încercaţi să obţineţi mai întâi relaţia

Puteti va rog sa mai explicati putin?Pentru ca feciorul meu si cu mine ne gandim de doua ore si 4 ni se pare ce e 3 si 2 ca e unu; de am ametit tot uitandu-ne la atatea patrate.
Multumim frumos!

Să numim "bună" o colorare care respectă cerinţa din enunţ.
Ideea este să considerăm o colorare bună a unui dreptunghi 2xk, şi să vedem cum pot fi colorate segmentele din ultimul dreptughiuleţ 2x1.

Acum, dintr-o colorare buna 2x(k-1), adăugând ultimul dreptunghi colorat cum am dedus mai sus, se obţine o colorare bună 2xk.

Şpilul este că sunt şi colorări 2x(k-1) care nu sunt bune, dar care, adăugând ultimul dreptunghi gol, devin bune. A se vedea desenul de mai jos. Câte sunt acestea?

Colorarile " ne-bune" care pot deveni bune sunt cele care au patratul de sus(ca in desen) sau cel de jos blocat.Daca ambele sunt blocate nu pot sa devina bune.Sau ma pacalesc?

[Citat] Colorarile "ne-bune" care pot deveni bune sunt cele care au patratul de sus (ca in desen) sau cel de jos blocat. Daca ambele sunt blocate nu pot sa devina bune. Sau ma pacalesc?

Sa fixam o colorare "ne-buna".
Sa notam primele doua patrate cu 1 si 2

1xxxxxx...
2xxxxxx...

si sa ocupam mai departe cu 1 si/sau (de fapt sau dijunctiv, colorarea fiind "ne-buna") 2 patratele in care putem ajunge din 1, respectiv 2.
Intre doua patrate alaturate avem o culoare "rosie sau alba", eu o sa ii spun "usa inchisa sau deschisa", corespunzator.

Atunci o astfel de colorare "ne-buna" devine buna adaugând doua camere AB cu "toate usile deschise" la inceput in

A1xxxxxx...
B2xxxxxx...

daca si numai daca ne aflam intr-o situatie din urmatoarele:

A1111...1222222222
B2222...2222222222

sau

A1111...1111111111
B2222...2111111111

sau

A1111...1111111111
B2222...2222222222

In primele doua cazuri am marcat cu verde primul punct care ne ajuta sa ne legam recursiv...

[Citat] Colorarile " ne-bune" care pot deveni bune sunt cele care au patratul de sus(ca in desen) sau cel de jos blocat.Daca ambele sunt blocate nu pot sa devina bune.Sau ma pacalesc?

Nu, e evident. Să observăm acum că avem

colorări care nu sunt bune cu "pătratul de sus blocat", şi tot atâtea cu cel de jos. Dar nu sunt astea singurele colorări care nu sunt bune şi care devin bune prin adăugarea dreptunghiului la final, nu?

[Citat] Dar nu sunt astea singurele colorări care nu sunt bune şi care devin bune prin adăugarea dreptunghiului la final, nu?

Cred ca nu,dar sunt singurele pe care la vad...Adica,mi se pare ca pana la ultimul dreptungiulet trebuie sa avem o colorare buna,si doar ultimul dreptunghi are voie sa fie colarat "gresit" ,ca apoi sa-l spargem prin adaugarea unui alt dreptunghi.

Gata!M-am prins!
Multumesc mult de tot!Astept acum sa vina musteriul sa o ducem la bun sfarsit(desi pana-l vad ca scrie linie de cod cred ca trece o saptamana

Pentru finalizare, după ce justificăm relaţia

scriem şi relaţia pentru k-1 în loc de k şi le scădem.

Vom obţine