2793 - Pozitii consecutive

Cerință

Considerăm următorul șir, în care n este un număr natural nenul:
fn = 0, daca n=1
fn = 3, daca n=2
fn = 2⋅fn−1–fn−2+2, dacă n>2.

Primii termeni ai acestui șir sunt: 0, 3, 8, 15, 24, 35, 48, 63, 80 ....

Se citesc două numere naturale din intervalul [0,10⁹], x și y, reprezentând valorile a doi termeni aflați pe poziții consecutive în șirul dat (x<y), și se cere să se afișeze, în ordine strict descrescătoare, separați prin câte un spațiu, toţi termenii șirului mai mici sau egali cu y.

Date de intrare

Fișierul de intrare pozitiiconsecutive.in conține pe prima linie numerele x y.

Date de ieșire

Fișierul de ieșire pozitiiconsecutive.out va conține pe prima linie în ordine strict descrescătoare, separați prin câte un spațiu, toţi termenii șirului mai mici sau egali cu y.

Restricții și precizări

Pentru determinarea și afișarea numerelor cerute se utilizează un algoritm eficient din punctul de vedere al spațiului de memorie și al timpului de executare; se recomandă evitarea memorării numerelor într-un tablou sau în altă structură de date similară n∈[1,10 ⁹ ]

Exemplu

Date de intrare: pozitiiconsecutive.in : 48 63
Date de ieșire: pozitiiconsecutive.out : 63 48 35 24 15 8 3 0

Rezolvare

<syntaxhighlight lang="python" line> if __name__ == "__main__":

   citire_fisier = open("pozitiiconsecutive.in" , "r")
   scriere_fisier = open("pozitiiconsecutive.out" , "w")
   x = int(citire_fisier.readline().strip())
   y = int(citire_fisier.readline().strip())
   z = 9
   scriere_fisier.write(str(y))
   scriere_fisier.write(' ')
   scriere_fisier.write(str(x))
   scriere_fisier.write(' ')
   while(z > 8):
       z = 2 * x - y + 2
       scriere_fisier.write(str(z))
       scriere_fisier.write(' ')
       y = x
       x = z
   scriere_fisier.write('3')
   scriere_fisier.write(' ')
   scriere_fisier.write('0')

</syntaxhighlight>