2202 - Extindere

Sursa: [1]

Cerinţa

Se consideră operația ': {1; 2} → {1; 2}, astfel încât 1 = 2, 2 = 1. Operația se extinde asupra oricărei secvențe formate cu cifre de 1 și 2, de exemplu 1211212121 =2122121212. Se consideră șirul infinit s format cu cifre de 1 și 2, generat incremental prin extindere după următoarea regulă de concatenare: s1 = 1221, s2 = 1221211221121221, … , sk+1 = sk sk sk sk, …, pentru orice număr natural nenul k.

Să se scrie un program care pentru un n număr natural nenul cunoscut determină și afișează a n-a cifră a șirului s, astfel încât numărul de pași ai programului să fie proporțional cu log2(n) (complexitate timp logaritmică în funcție de n).

Date de intrare

Programul conține pe prima linie numărul natural nenul n.

Date de ieșire

Programul va conține pe prima linie numărul c care reprezintă a n-a cifră a șirului format după regula precizată mai sus.

Dacă datele sunt introduse corect, programul va rula.

În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n ≤ 1.000.000

Exemplul 1

Intrare

18

Ieșire

1

Rezolvare

<syntaxhighlight lang="python" line>

1. 4273

def patrate_perfecte(n):

   patrate = []
   i = 1
   while len(patrate) < n:
       patrat = i * i
       patrate.append(patrat)
       i += 1
   return patrate

def calculeaza(numbers):

   product = 1
   for number in numbers:
       product *= number
   return product

def validare_numar(n):

   if n < 1 or n > 10:
       return False
   return True

if __name__ == '__main__':

   n = int(input("Introduceți numărul n: "))
   if not validare_numar(n):
       print("Datele introduse nu corespund cerintelor.")
   else:
       squares = patrate_perfecte(n)
       product = calculeaza(squares)
       print("Datele introduse corespund cerintelor.")
       print(product)

</syntaxhighlight>