Rezolvare PBinfo #2553

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 ≤ 1018;
• Se garantează că există o soluție pentru oricare n;

Exemplu:

Intrare

41

Ieșire

19

Explicație

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