3234 - Pavare 3: Diferență între versiuni
De la Universitas MediaWiki
Mraa (discuție | contribuții) (Pagină nouă: 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țin...) |
Mraa (discuție | contribuții) |
||
(Nu s-a afișat o versiune intermediară efectuată de același utilizator) | |||
Linia 21: | Linia 21: | ||
11 | 11 | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3" line="1"> | |||
MOD = 1000000007 | MOD = 1000000007 | ||
def numar_pavari(N): | 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__": | 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> |
Versiunea curentă din 11 ianuarie 2024 18:31
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")