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)中的位置

Sample Input

9 4

Sample Output

8

其实就是二分的思想,模拟的时候注意一下边界就可以了。

CODE

#include<stdio.h>
 
int main()
{
  int l,r,k,n,q;
  scanf("%d%d",&n,&q);
  l=n;r=1;
  while(l!=r)
    {
      q=(l+r-q);
      k=(l+r)/2;
      if(q>k)
	r=k+1;
      else
	l=k;
    }
  printf("%dn",q);
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>