Josephus

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ță.

Cerința

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ță.

Restricții și precizări

1 ≤ n ≤ 10¹⁸;
Se garantează că există o soluție pentru oricare n;

Exemplu

Intrare

Ieșire

Explicație

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Josephus:

#include <iostream>

using namespace std;

int log_2(unsigned long long x)
{
    int rez = 0;
    while(x) { x /= 2; ++rez; }
    return rez-1;
}

int main()
{
    unsigned long long n;
    cin >> n;

    // Orice numar n poate fi scris sub forma 2^a+l
    // Raspunsul pentru orice intrebare este l*2+1

    // Pe baza acestei observatii, exista doua posibilitati
    // de a calcula rezultatul

    // 1. Calculam efectiv l*2+1
    // 2. Mutam primul bit de 1 (citind numarul de la stanga la dreapta)
    //    si il ducem in coada

    // Solutia 1:
    cout << (n - ((unsigned long long)1 << (unsigned long long)log_2(n))) * 2 + 1;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2553 Josephus

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2553 Josephus de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2553 Josephus