标签存档: SGU175

SGU 175 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=175

175.Encoding

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

Let phi(W) is the result of encoding for algorithm:
1.If the length of W is 1 then phi(W) is W;
2.Let coded word is W = w1w2...wN and K = N / 2 (rounded down);
3.phi(W) = phi(wNwN-1...wK+1) + phi(wKwK-1...w1).
For example, phi('Ok') = 'kO', phi('abcd') = 'cdab'.
Your task is to find position of letter wq in encoded word phi(W).

令phi(W)为字符串W按以下方法编码的结果:
1、如果W长度为1,那么phi(W)就是W
2、设W=w1 w2 …… wN 且 K=N/2 (向下取整)
3、phi(W)=phi(wN wN-1 …… wK+1)+phi(wK wK-1 …… w1)
例如,phi('Ok')='kO',phi('abcd')='cdab'。
你的任务就是找到原字符串W内第q个字符wq在编码后的字符串phi(W)中的位置。

Input

Given integers N, q (1 <= N <= 10^9; 1<= q <= N), where N is the length of word W.

整数N,q(1<=N<=10^9;1<=q<=N),其中N是字符串W的长度

Output

Write position of letter wq in encoded word phi(W).

输出wq在编码后的字符串phi(W)中的位置

继续阅读 »