题目描述

设phi(W)为以下编码算法的结果：

1. 若W的长度为1，则phi(W)=W；

2. 设编码单词为W=w1w2…wN，K=N/2（向下取整）；

3. phi(W) = phi(wNw(N-1)…w(K+1)) + phi(wKw(K-1)…w1)。

例如，phi(‘Ok’)=’kO’，phi(‘abcd’)=’cdab’。

你的任务是找出字母Wq在加密的单词phi(W)中的位置。

 

输入：

给出整数N和q (1<=N<=10^9； 1<=q<=N)，N是单词W的长度。

输出：

输出字母Wq在加密的单词phi(W)中的位置。

样例测试：

输入：

9 4

输出：

8

 

program sky;

var

   n,ans : longint;

procedure get(l,r: longint );

var

   mid : longint;

begin

   if l=r then exit;

   mid:=(r-l+1) shr 1+l-1;

   if ans<=mid then

   begin

      ans:=l+mid-ans;

      inc(ans,r-mid);

      get(r+1-(mid-l+1),r);

   end

   else

   begin

      ans:=mid+1+(r-ans);

      dec(ans,mid-l+1);

      get(l,l-1+(r-mid));

   end;

end;

begin

   read(n,ans);

   get(1,n);

   writeln(ans);

end.

 

毫无难度的递归模拟仅写给像我一样的细节爱出问题的盆友。

长度=r-l+1

左端点加上长度=(l-1)+(l-r+1)

右端点减去长度=(r+1)-(l-r+1)

仅写给自己吧。。