2553 - Josephus

Cerința

Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic!

Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață.

Josephus ar fi preferat să se predea. Pe ce poziție ar fi trebuit să se afle soldatul pentru a putea realiza acest lucru?

Date de intrare

Se va citi un singur număr natural nenul, n.

Date de ieșire

Se va afișa un singur număr ce reprezintă poziția pe care Josephus trebuia să se afle pentru a rămâne în viață, alături de un mesaj de validare a datelor introduse ("Input valid"; se afișează "n trebuie să fie între i și 10^18" în caz contrar).

Restricții și precizări

• 1 ≤ n ≤ 1018;
• Se garantează că există o soluție pentru oricare n;

Exemplu

Intrare

41

Ieșire

Input valid

19

Explicație

1 ⇒ 2
3 ⇒ 4
…
39 ⇒ 40
41 ⇒ 1
3 ⇒ 5
…
39 ⇒ 41
3 ⇒ 7
11 ⇒ 15
………
19 ⇒ 35

Rezolvare

def calculate_exponent(n):
    exponent = 0
    save_n = n
    while save_n != 1:
        save_n //= 2
        exponent += 1
    return exponent

def is_power_of_two(n):
    exponent = calculate_exponent(n)
    return (1 << exponent) == n

def calculate_result(n):
    exponent = calculate_exponent(n)
    if is_power_of_two(n):
        return 1
    else:
        return ((n - (1 << exponent)) << 1) + 1

def validate_n(n):
    if not 1 <= n <= 10**18:
        raise ValueError("n trebuie să fie între i și 10^18")
    else:
        print("Input valid")

if __name__ == "__main__":
    n = int(input())
    validate_n(n)
    print(calculate_result(n))

Explicație cod

Acest program implementează trei funcții care lucrează împreună pentru a verifica dacă un număr întreg n este o putere a lui 2 și pentru a calcula un rezultat bazat pe n.

Funcția "calculate_exponent" primește un număr întreg n și calculează exponentul său în baza 2. Exponentul este calculat prin împărțirea repetată a lui n la 2 până când n ajunge la valoarea 1, numărul de împărțiri fiind exponentul.

Funcția "is_power_of_two" primește un număr întreg n și verifică dacă este o putere a lui 2, comparându-l cu 2 ridicat la exponentul calculat în funcția anterioară.

Funcția "calculate_result" primește un număr întreg n și calculează rezultatul bazat pe aceasta. Dacă n este o putere a lui 2, rezultatul va fi 1, altfel va fi calculat după o formulă dată.

Funcția "validate_n" primește un număr întreg n și verifică dacă se încadrează între 1 și 10^18 inclusiv. Dacă n nu se încadrează în această plajă, funcția va arunca o excepție "ValueError".

În metoda "main", se primește un număr întreg n de la utilizator, se validează și se calculează și se afișează rezultatul apelând funcția "calculate_result".