1159 - Smen

Cerința

Se dă un șir V. Știind V0 = 3 și regula de formare a șirului:

Vi = ([Vi-1*Vi-1 / (i + 2)] + Vi-1 * i + i + 1) % 666013.

să se determine al n-lea termen al șirului. (unde [x] reprezintă partea întreagă a numărului x)

Date de intrare

Fișierul de intrare smen.in conține numărul n.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pe următorul rând se va afișa al n-lea termen al șirului.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 1 ≤ n ≤ 20.000.000

Exemplu 1

Intrare

10000000

Ieșire

Datele de intrare corespund restricțiilor impuse.

22230

Exemplu 2

Intrare

21345670

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 1159 Smen

def conditii(n):

   return 1 <= n <= 20_000_000

def smen(n):

   # v_n = valoarea de la pasul n
   # v_i = valoarea de la pasul i
   # Primul termen al șirului este 3
   v_n, v_i = 3, 0
   for i in range(n + 1):
       # Formula de recurență, conform cerinței
       v_i = ((v_n * v_n // (i + 2)) + v_n * i + i + 1) % 666013
       # Înlocuim v_n cu v_i pentru a putea calcula următorul termen
       v_n = v_i

   # Afisăm al n-lea termen
   print(v_i)

if __name__ == "__main__":

   n = int(input())

   if not conditii(n):
       print("Datele de intrare nu corespund restricțiilor impuse.")
   else:
       print("Datele de intrare corespund restricțiilor impuse.")
       smen(n)

</syntaxhighlight>