Strange Counter:
Bob has a strange counter. At the first second,t=1 it displays the number 3. At each subsequent second, the number displayed by the counter decrements by 1.The counter counts down in cycles. In the second after the counter counts down to 1 the number becomes 2x he initial number for that countdown cycle and then continues counting down from the new initial number in a new cycle. The diagram below shows the counter values for each time t in the first three cycles:
Given a time,t , find and print the value displayed by the counter at time t.
Input Format
A single integer denoting the value of t.
Output Format
Print the value displayed by the strange counter at the given time t
Constraints:
- 1<= t <=\(10^{12}\)
Subtask:
- 1<= t <=\(10^{5}\) 60% of the maximum score.
Sample Input
4
Sample Output
6
Explanation
Time t=4 marks the beginning of the second cycle in which the counter displays a number that is double the initial number displayed at the beginning of the previous cycle (i.e., 2x3 = 6).This is also shown in the diagram in the Problem Statement above.
Solution
#!/bin/python
'''we know the initial values of time and value are 1 and 3 respectively. You were also told that at each step the
value gets doubled. Look at the example and you'll see that the next counter starts at time + value.If you look carefully, the last 'time' value of cycle 1 is 3 which is 3*1=3*(2^1-1), the last 'time' value of cycle 2 is 9 which is 3*3=3*(2^2-1), the last 'time' value of cycle 3 is 21 which is 3*7=3*(2^3-1).
So, we should keep doubling n, which represents the 2^1, 2^2, 2^3 part. Hence the while loop. The loop stops when it reaches to a cycle whose max time is bigger than the real time t, then we know that it has reached the last cycle.
And taking the second cycle as an example, 'time' 7 has 'value' 3, and the max time of the second cycle is 9. We find the relationship between them is 3 = 9 - 7 + 1, which is why we print (3 * (n - 1) - t + 1) to get the output of 3 when t is 7.'''
import sys
t = int(raw_input().strip())
value = 3
while t > value:
t = t-value
value *= 2
print(value-t+1)