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, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou 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).

În caz contrar, 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. 2202

import math

def build_sequence(n):

   k = 1
   s = '1221'
   while 2**k < n:
       s_new = 
       for i in range(len(s)):
           if s[i] == '1':
               s_new += '12'
           else:
               s_new += '21'
       s = s_new
       k += 1
   return s

def find_digit(n, s):

   pos = 0
   for i in range(len(s)):
       if pos == n-1:
           return s[i]
       pos += 1
       if pos >= len(s):
           pos = 0
           s *= k

if __name__ == '__main__':

   n = int(input("Introdu un nr. :"))
   s = build_sequence(n)
   print(find_digit(n, s))

</syntaxhighlight>

Explicatie cod:

Acest cod definește două funcții: build_sequence(n) și find_digit(n, s). Funcția build_sequence(n) primește un număr natural n și construiește secvența de cifre specificată în enunț folosind regula dată. Aceasta crește lungimea șirului cu fiecare iterație, până când șirul are cel puțin n cifre. Funcția find_digit(n, s) primește numărul n și șirul de cifre s și găsește și returnează cifra de pe poziția n din șirul s.

La final, se verifică dacă programul rulează ca modul principal cu ajutorul declarației if __name__ == '__main__':. Dacă acesta este cazul, programul va citi un număr n de la utilizator, va construi șirul specificat și va găsi și afișa cifra de pe poziția n din șir folosind cele două funcții definite anterior.