Codeforces Round 608 (Div. 2) |
---|
Finished |
At first, let's define function f(x) as follows: f(x)={x2if x is evenx−1otherwise
We can see that if we choose some value v and will apply function f to it, then apply f to f(v), and so on, we'll eventually get 1. Let's write down all values we get in this process in a list and denote this list as path(v). For example, path(1)=[1], path(15)=[15,14,7,6,3,2,1], path(32)=[32,16,8,4,2,1].
Let's write all lists path(x) for every x from 1 to n. The question is next: what is the maximum value y such that y is contained in at least k different lists path(x)?
Formally speaking, you need to find maximum y such that |{x | 1≤x≤n,y∈path(x)}|≥k.
The first line contains two integers n and k (1≤k≤n≤1018).
Print the only integer — the maximum value that is contained in at least k paths.
11 3
5
11 6
4
20 20
1
14 5
6
1000000 100
31248
In the first example, the answer is 5, since 5 occurs in path(5), path(10) and path(11).
In the second example, the answer is 4, since 4 occurs in path(4), path(5), path(8), path(9), path(10) and path(11).
In the third example n=k, so the answer is 1, since 1 is the only number occuring in all paths for integers from 1 to 20.
Name |
---|