问题 4869 --2.加密函数

4869: 2.加密函数

题目描述

  小明写了一封情书,为了防止被别人发现,他设计了一个加密函数 $phi$。
我们可以认为情书为一个字符串 $W,N$, 为字符串的长度,设 $phi(W)$为加密后的字符串:
  1. 如果 $W$ 的长度为 1,那么 $phi(W)=W$;
  2. 设 $W=w_1w_2 \dots w_N$,令 $K=\lfloor \frac{N}{2}\rfloor$,$phi(W)=phi(w_Nw_N-1 \dots w_{K+1})+phi(w_Kw_{K-1} \dots w_1)$。
举个例子, $phi("Ok") = "kO"$,$phi("abcd") = "cdab"$ 。 现在小军截获了小明的情书,他想破译这封情书。现在他交给你这个任务,询问原字符串的第 $q$ 个字符在加密后的字符串中的位置。

输入

输入两个整数 $N,q$。

输出

仅一行,表示第 $q$ 个字符加密后的位置。

样例输入输出

输入#1 复制
9 4
输出#1 复制
8

提示

对于 $30\%$ 数据,$1 \leq q \leq N \leq 10^3$;
对于 $100\%$ 数据,$1 \leq q \leq N \leq 10^9$。


序号 标题 作者 发表时间 费用 订购数 操作