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"> 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>