Oros Ioana Diana at 13:11, 18 May 2024

2024-05-18T13:11:14Z

Oros Ioana Diana: Pagină nouă: == Enunț == Ana Mia are o recurență liniară de forma P[N] = A[1]P[N-1] + A[2]P[N-2] + A[3]P[N-3] + A[4]P[N-4], N ≥ 5. Studiind-o, îi vine o idee MAXIMĂ de problemă: “Pentru câte cvadriplete (P[1], P[2], P[3], P[4]) din mulțimea numerelor naturale [1, B] valoarea P[N] modulo K are valoarea X?” == Cerința == Scrieți un program care citind N, B, X, K, și numerele A[i], 1 ≤ i ≤ 4 rezolvă problema Anei. == Date de intrare == Fișierul de intrare reccin....

2024-01-08T21:45:29Z

Pagină nouă: == Enunț == Ana Mia are o recurență liniară de forma P[N] = A[1]*P[N-1] + A[2]*P[N-2] + A[3]*P[N-3] + A[4]*P[N-4], N ≥ 5. Studiind-o, îi vine o idee MAXIMĂ de problemă: “Pentru câte cvadriplete (P[1], P[2], P[3], P[4]) din mulțimea numerelor naturale [1, B] valoarea P[N] modulo K are valoarea X?” == Cerința == Scrieți un program care citind N, B, X, K, și numerele A[i], 1 ≤ i ≤ 4 rezolvă problema Anei. == Date de intrare == Fișierul de intrare reccin....

New page

== Enunț ==
Ana Mia are o recurență liniară de forma P[N] = A[1]*P[N-1] + A[2]*P[N-2] + A[3]*P[N-3] + A[4]*P[N-4], N ≥ 5. Studiind-o, îi vine o idee MAXIMĂ de problemă: “Pentru câte cvadriplete (P[1], P[2], P[3], P[4]) din mulțimea numerelor naturale [1, B] valoarea P[N] modulo K are valoarea X?”
== Cerința ==
Scrieți un program care citind N, B, X, K, și numerele A[i], 1 ≤ i ≤ 4 rezolvă problema Anei.
== Date de intrare ==
Fișierul de intrare reccin.txt conține pe prima linie numerele N, B, X, K, separate printr-un spațiu, iar pe a doua linie 4 numere naturale separate prin spații, reprezentând numerele A[i], 1 ≤ i ≤ 4.
== Date de ieșire ==
Fișierul de ieșire reccout.txt va conține pe prima linie numărul ANS, răspunsul problemei puse de Ana Mia.
== Restricții și precizări ==
*'''5 ≤ N ≤ 10^18'''
*'''1 ≤ B ≤ 1000'''
*'''1 ≤ K ≤ 10^9'''
*'''0 ≤ X < K'''
*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
== Exemplul 1 ==
; reccin.txt
: 6 2 3 4
: 1 2 3 1
; reccout.txt
: 2
<br>
== Exemplul 2 ==
; reccin.txt
: 8 5 1 7
: 2 1 3 2
; reccout.txt
: 4
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#2493 - Recc
def count_quadruplets(N, B, X, K, A):
if not (5 <= N <= 10**18) or not (1 <= B <= 1000) or not (1 <= K <= 10**9) or not (0 <= X < K):
return "Fals"

if N == 1:
return 1 if X % K == A[0] else 0

dp = [0] * (B + 1)

for i in range(1, B + 1):
dp[i] = (A[0] * dp[i - 1]) % K

if i >= 2:
dp[i] = (dp[i] + A[1] * dp[i - 2]) % K

if i >= 3:
dp[i] = (dp[i] + A[2] * dp[i - 3]) % K

if i >= 4:
dp[i] = (dp[i] + A[3] * dp[i - 4]) % K

ans = 0
for i in range(1, B + 1):
if (dp[i] + X) % K == 0:
ans += 1

return ans

def main():
with open("reccin.txt", "r") as f:
N, B, X, K = map(int, f.readline().split())
A = list(map(int, f.readline().split()))

result = count_quadruplets(N, B, X, K, A)

with open("reccout.txt", "w") as f_out:
f_out.write(str(result))

if __name__ == "__main__":
main()

</syntaxhighlight>

== Explicatie ==
Soluțiile sunt (2, 1, 2, 1) și (2, 2, 2, 1)

2493 - Recc - Revision history

Oros Ioana Diana at 13:11, 18 May 2024