Description
Chloe, the same as Vladik, is a competitive programmer. She didn't have any problems to get to the olympiad like Vladik, but she was confused by the task proposed on the olympiad.
Let's consider the following algorithm of generating a sequence of integers. Initially we have a sequence consisting of a single element equal to 1. Then we perform (n - 1) steps. On each step we take the sequence we've got on the previous step, append it to the end of itself and insert in the middle the minimum positive integer we haven't used before. For example, we get the sequence [1, 2, 1] after the first step, the sequence [1, 2, 1, 3, 1, 2, 1] after the second step.
The task is to find the value of the element with index k (the elements are numbered from 1) in the obtained sequence, i. e. after (n - 1)steps.
Please help Chloe to solve the problem!
Input
The only line contains two integers n and k (1 ≤ n ≤ 50, 1 ≤ k ≤ 2n - 1).
Output
Print single integer — the integer at the k-th position in the obtained sequence.
Sample Input
3 2 4 8
Sample Output
2 4
Note
In the first sample the obtained sequence is [1, 2, 1, 3, 1, 2, 1]. The number on the second position is 2.
In the second sample the obtained sequence is [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]. The number on the eighth position is 4.
思路
题意：
有一个序列，由1 - n 的数字组成，第一个元素是 1 ，接下来把前一步所得到的序列加在后面并且在这两个序列中间插上n个数中未使用过的最小数，问第k个数是什么。
题解:
将序列写出来可以发现规律，1 + 2x 的位置值都是 1，2 + 4x 的位置的值都是 2，4 + 8x 的位置的数都是 3，8 + 16x 的位置的数都是 4……，因此按照这个规律就可以知道第k个数是谁了。
#include<bits/stdc++.h>
using namespace std;
typedef __int64 LL;
LL pow(LL x,LL n)
{
LL res = 1;
while (n)
{
if (n & 1)
{
res = res*x;
}
x *= x;
n >>= 1;
}
return res;
}
int main()
{
LL n,k;
scanf("%I64d%I64d",&n,&k);
for (int i = 0;;i++)
{
LL tmp = pow(2,i);
if ((k - tmp) % (tmp*2) == 0)
{
printf("%d\n",i+1);
break;
}
}
return 0;
}
递归求解
#include<bits/stdc++.h>
using namespace std;
typedef __int64 ll;
int work(ll n,ll k)
{
ll p=pow(2,n-1);
if(k>p) work(n-1,k-p);
else if(k<p) work(n-1,k);
else return n;
}
int main()
{
ll n,k;
cin>>n>>k;
cout<<work(n,k)<<endl;
return 0;
}