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 == 
 
Dacă datele sunt introduse corect, pe ecran se va afișa: 
'''"Datele sunt introduse corect."''', apoi ''' fișierul beta.out va conține valoarea cerută. Dacă șirul B are mai puțin de poz elemente se va scrie în fișier -1.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

== 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 1 ==
; Intrare
: beta.in
: 8 13
; Ieșire
: Datele sunt introduse correct.
: beta.out
: 7

== Exemplu 2 ==
; Intrare
: beta.in
: 8 25
; Ieșire
: Datele nu corespund restricțiilor impuse.




== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3357 - beta
def calc_b(n, k):
    b = list(range(1, n+1))
    p = n
    while p > 1:
        p //= 2
        q = n // p
        r = n % p
        if r == 0:
            r = p
            q -= 1
        start = n - q*p + 1
        end = start + r - 1
        if q % 2 == 1:
            b.extend(reversed(range(start, end+1)))
        else:
            b.extend(range(start, end+1))
    return b

def validate_input(n, k):
    if not (1 <= n <= 10**5 and 1 <= k <= n):
        return False
    return True

if __name__ == '__main__':
    with open('beta.in', 'r') as f_in, open('beta.out', 'w') as f_out:
        n, k = map(int, f_in.readline().split())
        if not validate_input(n, k):
            f_out.write('-1\n')
            print('Datele nu corespund restricțiilor impuse.')
        else:
            b = calc_b(n, k)
            f_out.write(f'{b[k-1]}\n')





</syntaxhighlight>
== Explicatie Rezolvare ==

Funcția `calc_b` primește două argumente: `n`, care este numărul dat, și `k`, care este poziția cerută în șirul `B`. Funcția începe prin construirea șirului `A`, care este un șir ordonat de la 1 la `n`. Apoi se împarte `n` la 2, apoi la 4, apoi la 8, și așa mai departe, până când nu se mai poate împărți. Se păstrează ultimele `n/p` elemente din șirul `A`, și acestea sunt adăugate la șirul `B` în ordinea cerută. Dacă `n` nu se divide exact la `p`, atunci se ia o bucată mai mică din șirul `A` și se adaugă la șirul `B` în ordinea cerută. Funcția se termină returnând șirul `B`.

Funcția `validate_input` primește aceiași doi parametri ca și `calc_b` și verifică dacă aceștia îndeplinesc condițiile date în enunțul problemei. Dacă nu se îndeplinesc, returnează `False`, altfel returnează `True`.

Funcția `main` citește datele de intrare din fișierul `beta.in`, validează datele, calculează șirul `B` folosind funcția `calc_b`, și scrie în fișierul `beta.out` numărul de pe poziția `k` din șirul `B`. Dacă datele nu sunt valide, se scrie `-1` în fișierul `beta.out` și se afișează un mesaj de eroare.