1031 - Culori2

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:

1. Dacă o scândură era vopsită cu alb, următoarea scândură o vopsea obligatoriu cu albastru
2. Dacă o scândură era vopsită cu albastru, atunci următoarea scândură o vopsea cu alb sau roşu
3. Dacă o scândură era vopsită cu roşu, atunci următoarea scândură o vopsea cu albastru sau verde
4. Dacă o scândură era vopsită cu verde, atunci următoarea scândură o vopsea cu roșu sau galben
5. 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.

Cerința

Ajutați-o pe Miruna să găsească răspunsul la întrebarea sa.

Date de intrare

Fișierul de intrare culori2in.txt conține pe prima sa linie un singur număr natural N (1 ≤ N ≤ 5000).

Date de ieșire

Fișierul de ieșire culori2out.txt 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.

Restricții și precizări

• 1 ≤ N ≤ 5000
• Pentru 25% dintre teste N≤45.

Exemplu 1:

culori2in.txt

4

culori2out.txt

24

Exemplu 2:

culori2in.txt

0

culori2out.txt

Datele de intrare nu au fost respectate.

Rezolvare

def numar_moduri_vopsire_gard(N):
    # Inițializăm un dicționar pentru a stoca numărul de moduri posibile
    # pentru fiecare culoare și fiecare poziție
    moduri = {
        'alb': [0] * (N + 1),
        'albastru': [0] * (N + 1),
        'rosu': [0] * (N + 1),
        'verde': [0] * (N + 1),
        'galben': [0] * (N + 1)
    }

    # Pentru prima scândură, fiecare culoare este o opțiune validă
    for culoare in moduri.keys():
        moduri[culoare][1] = 1

    # Calculăm numărul de moduri pentru fiecare poziție și culoare
    for i in range(2, N + 1):
        moduri['alb'][i] = moduri['albastru'][i - 1]
        moduri['albastru'][i] = moduri['alb'][i - 1] + moduri['rosu'][i - 1]
        moduri['rosu'][i] = moduri['albastru'][i - 1] + moduri['verde'][i - 1]
        moduri['verde'][i] = moduri['rosu'][i - 1] + moduri['galben'][i - 1]
        moduri['galben'][i] = moduri['verde'][i - 1]

    # Sumăm modurile pentru toate culorile pentru a obține rezultatul final
    rezultat = sum(moduri[culoare][N] for culoare in moduri.keys())
    return rezultat


def main():
    try:
        with open("culori2in.txt", "r") as file_in:
            N = int(file_in.readline().strip())

            if 1 <= N <= 5000:
                rezultat = numar_moduri_vopsire_gard(N)

                with open("culori2out.txt", "w") as file_out:
                    file_out.write(str(rezultat))
            else:
                print("Datele de intrare nu au fost respectate.")
    except Exception as e:
        print(f"Nu au fost respectate cerințele impuse: {e}")


if __name__ == "__main__":
    main()