Editing 2202 - Extindere

Sursa: [https://www.pbinfo.ro/probleme/4273/prodpp]
== 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 ==
; Datele de intrare
: Introdu un nr. :
: 18
; Datele de ieșire
: Datele sunt introduse corect.
: 1
<br>

== Rezolvare == 
<syntaxhighlight lang="python" line>
#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

def validate_input(n):
    if n <= 0 or not isinstance(n, int):
        return False
    else:
        return True

if __name__ == '__main__':
    n = int(input("Introdu un nr. :"))
    if validate_input(n):
        print("Datele sunt introduse corect.")
        s = build_sequence(n)
        print(find_digit(n, s))
    else:
        print("Datele nu corespund restricțiilor impuse.")

</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.