Editing 3357 - beta

Sursa: [https://www.pbinfo.ro/probleme/3357/beta3357 - beta]
----
== Cerinţa ==
Se dă un număr natural n despre care se cunoaște că este putere de 2. Considerăm inițial șirul numerelor naturale de la 1 la n așezate în ordine crescătoare. Notăm cu A acest șir. Pornind de la acesta, se construiește un nou șir (să îl notăm cu B) astfel: Primele n elemente ale lui B sunt chiar elementele șirului A în aceeași ordine. Următoarele n/2 elemente ale lui B sunt ultimele n/2 elemente ale lui A dar scrise în ordine inversă (descrescător). Următoarele n/4 elemente ale lui B sunt ultimele n/4 elemente ale lui A scrise în ordine crescătoare, următoarele n/8 elemente ale lui B sunt ultimele n/8 elemente ale lui A scrise în ordine descrescătoare, și tot așa, cu fiecare putere de 2 (notată p) ce apare la numitor, luăm ultimele n/p elemente din A și le adăugăm la finalul lui B alternând ordinea de parcurgere, de la o putere la alta conform modului descris mai sus. Se mai să un număr poz. Se cere determinarea numărului de pe poziția poz din șirul B.


== Date de intrare ==
Fișierul beta.in conține pe prima linie numerele naturale n și poz separate printr-un spațiu.


== Date de ieșire == 
Fișierul beta.out conține valoarea cerută. Dacă șirul B are mai puțin de poz elemente se va scrie în fișier -1.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 1.000.000.000
* n se dă putere de 2
* 1 ≤ poz ≤ 2.000.000.000
* Pentru 55 de puncte avem n ≤ 100.000
== Exemplu ==
; Intrare
: 8 13
; Ieșire
: 7

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3357 - beta
def generate_B(n):
    B = list(range(1, n+1))  # cream o lista cu elementele initiale din A
    for p in range(1, n.bit_length()):  # parcurgem puterile de 2 de la 1 la log2(n)
        last_n_p = B[-n//2**p:]  # luam ultimele n/p elemente din A
        if p % 2 == 1:  # daca puterea este impara, le adaugam in ordine inversa
            B += last_n_p[::-1]
        else:  # daca puterea este para, le adaugam in ordine crescatoare
            B += last_n_p
    return B

def validate_input(n, poz):
    if poz <= 0 or poz > n*2:
        print("-1")  # afisam -1 daca pozitia este invalida
        exit()

def solve(n, poz):
    B = generate_B(n)
    validate_input(len(B), poz)
    return B[poz-1]  # returnam elementul de pe pozitia ceruta (indexarea incepe de la 0)

if __name__ == "__main__":
    n, poz = map(int, input().split())
    print(solve(n, poz))


</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția generate_B(n) generează șirul B conform algoritmului descris în cerință. Folosim metoda bit_length() pentru a determina numărul de puteri de 2 (adica p) necesare pentru a completa șirul B. Apoi, pentru fiecare putere de 2, luăm ultimele n/p elemente din A și le adăugăm la finalul lui B în funcție de paritatea lui p.

Funcția validate_input(n, poz) verifică dacă poziția dată este validă și afișează -1 dacă nu este.

Funcția solve(n, poz) este funcția principală care apelează celelalte două funcții și returnează elementul de pe poziția dată.

În blocul if __name__ == "__main__": citim datele de intrare și apelăm funcția solve(), apoi afișăm rezultatul.