DANGER - In Danger


Flavius Josephus and 40 fellow rebels were trapped by the Romans. His companions preferred suicide to surrender, so they decided to form a circle and to kill every third person and to proceed around the circle until no one was left. Josephus was not excited by the idea of killing himself, so he calculated the position to be the last man standing (and then he did not commit suicide since nobody could watch).

We will consider a variant of this "game" where every second person leaves. And of course there will be more than 41 persons, for we now have computers. You have to calculate the safe position. Be careful because we might apply your program to calculate the winner of this contest!

Input Specification

The input contains several test cases. Each specifies a number n, denoting the number of persons participating in the game. To make things more difficult, it always has the format "xyez" with the following semantics: when n is written down in decimal notation, its first digit is x, its second digit is y, and then follow z zeros. Whereas 0<=x,y<=9, the number of zeros is 0<=z<=6. You may assume that n>0. The last test case is followed by the string 00e0.

Output Specification

For each test case generate a line containing the position of the person who survives. Assume that the participants have serial numbers from 1 to n and that the counting starts with person 1, i.e., the first person leaving is the one with number 2. For example, if there are 5 persons in the circle, counting proceeds as 2, 4, 1, 5 and person 3 is staying alive.

Sample Input

05e0
01e1
42e0
66e6
00e0

Sample Output

3
5
21
64891137

hide comments
l0gic_b0mb: 2017-08-24 12:00:51

I don't think that finding pattern was the motto of this problem.
Solving the problem by breaking it into subproblems is much more elegant and fun.

prabodh prakash: 2017-05-01 10:27:32

Time limit must be more restrained.

vladimira: 2017-03-13 02:33:26

Its very useful to solve smth like this occasionally. Write brute force and print results from 1 to 50 and then look for pattern.

nilabja16180: 2017-03-04 17:01:16

Typo costed 1 WA!
Get the pattern its easy, used power of bits!

shubham_cs_iet: 2017-01-14 12:53:17

n=2, ans=1. costed me 2 WA :(... same logic as in http://www.spoj.com/problems/VECTAR10/.

cs_abhi2000: 2017-01-08 16:48:26

just find pattern and write code effectiently :)

mishra_sharad: 2016-08-16 15:07:00

if u have got the pattern then just properly write correct code....nothing special it has other than pattern.....AC in first try

sarthak_8: 2016-07-22 01:51:02

Don't look for a solution. Observe. Its easier than you think.

Rahadian Koesdijarto Putra: 2016-07-04 18:13:36

AC in one go! Took 40 minutes just to find the formula. Hint: Logarithm is your friend :)

PS: I used floor(sqrt(X)), and realized I fucked up!

lt: 2016-06-19 07:37:30

AC in one shot, but it took about two hours to figure out the pattern!!!


Added by:Wanderley Guimarăes
Date:2007-09-19
Time limit:0.75s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:University of Ulm Local Contest 2004