Editing 3234 - Pavare 3


Se dă un dreptunghi cu lungimea egală cu 2N centimetri și lățimea egală cu 3 centimetri.

==Cerința==
Să se determine numărul M al pavărilor distincte cu dale dreptunghiulare care au lungimea egală cu un centimetru și lățimea egală cu 2 centimetri.

==Date de intrare==
Fișierul de intrare pavare.in conține pe prima linie numărul natural nenul N, reprezentând jumătatea lungimii dreptunghiului.

==Date de ieșire==
Fișierul de ieșire pavare.out va conține pe prima linie numărul natural nenul, reprezentând numărul modalităților de a pava dreptunghiul.

==Restricții și precizări==
1 ≤ n ≤ 100
==Exemplu==:
pavare.in

2
pavare.out

11
==Rezolvare==
MOD = 1000000007

def numar_pavari(N):
    # Inițializăm lista dp cu 0-uri
    dp = [0] * (N + 1)

    # Prima poziție este 1, deoarece există o singură modalitate de a avea dreptunghiul nefragmentat
    dp[0] = 1

    # Calculăm numărul de modalități
    for i in range(1, N + 1):
        dp[i] = (3 * dp[i - 1]) % MOD
        if i >= 2:
            dp[i] = (dp[i] + dp[i - 2]) % MOD

    return dp[N]

if __name__ == "__main__":
    with open("pavare.in", "r") as f:
        N = int(f.readline())

    rezultat = numar_pavari(N)

    with open("pavare.out", "w") as g:
        g.write(str(rezultat) + "\n")
python pavare.py