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==
<syntaxhighlight lang="python3" line="1">
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")
</syntaxhighlight>