Question

Pasiunea Mirunei este să coloreze. Vacanţa trecută şi-a petrecut-o la bunica ei la ţară şi pentru că se cam plictisea s-a gândit să vopsească gardul de la casa bunicii.

Gardul este compus din N scânduri dispuse una lângă alta. Miruna a găsit în garajul bunicii 5 cutii de vopsea de culori diferite: albă, albastră, roşie, verde şi galbenă. Când a vopsit gardul, Miruna a respectat următoarele reguli:

Dacă o scândură era vopsită cu alb, următoarea scândură o vopsea obligatoriu cu albastru
Dacă o scândură era vopsită cu albastru, atunci următoarea scândură o vopsea cu alb sau roşu
Dacă o scândură era vopsită cu roşu, atunci următoarea scândură o vopsea cu albastru sau verde
Dacă o scândură era vopsită cu verde, atunci următoarea scândură o vopsea cu roșu sau galben
Dacă o scândură era vopsită cu galben, atunci următoarea scândură o vopsea obligatoriu cu verde
După ce a și-a terminat treaba Miruna își admira “opera de artă” și se întreba în câte moduri diferite ar fi putut să vopsească gardul bunicii.

DATE DE INTRARE
Fișierul de intrare culori2.in conține pe prima sa linie un singur număr natural N (1 ≤ N ≤ 5000).

DATE DE IESIRE
Fișierul de ieșire culori2.out va conţine pe prima sa linie un singur număr întreg reprezentând numărul de moduri diferite în care Miruna ar fi putut să vopsească gardul bunicii.

RESTRICTII SI PRECIZARI
1 ≤ N ≤ 5000
Pentru 25% dintre teste N≤45.

Nu vreau solutia printr-o recursivitate simpla, pentru ca dureaza prea mult.

Answer 1

Ai atasata sursa C++

71fe466d6107f00d91837b935312d3b8.cpp