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 "xy
ez
" 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
harry_shit:
20200116 13:27:08
O(1) solution 

m_______7:
20190328 14:35:24
How to solve with DP? Any hints please? Last edit: 20190328 14:36:09 

sh0w_st0pper:
20190121 08:07:01
Magic with Bits. Observe Pattern for powers of 2. 

masterchef2209:
20181018 12:02:30
this video will give insight for the problem https://www.youtube.com/watch?v=uCsD3ZGzMgE


adityad1998:
20180628 17:40:04
Just look for the pattern till 17or18. Simple AC. 

l0gic_b0mb:
20170824 12:00:51
I don't think that finding pattern was the motto of this problem.


prabodh prakash:
20170501 10:27:32
Time limit must be more restrained. 

vladimira:
20170313 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:
20170304 17:01:16
Typo costed 1 WA!


shubham_cs_iet:
20170114 12:53:17
n=2, ans=1. costed me 2 WA :(... same logic as in http://www.spoj.com/problems/VECTAR10/. 
Added by:  Wanderley GuimarÄƒes 
Date:  20070919 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  University of Ulm Local Contest 2004 