In Programming Land, there are several pathways called Philosopher’s Walks for philosophers to have a rest. A Philosopher’s Walk is a pathway in a square-shaped region with plenty of woods. The woods are helpful for philosophers to think, but they planted so densely like a maze that they lost their ways in the maze of woods of a Philosopher’s Walk.

Fortunately, the structures of all Philosopher’s Walks are similar; the structure of a Philosopher’s Walk is designed and constructed according to the same rule in a 2k meter square. The rule for designing the pathway is to take a right-turn in 90 degrees after every 1-meter step when k is 1, and the bigger one for which the integer k is greater than 1 is built up using four sub-pathways with k - 1 in a fractal style. Figure F.1 shows three Philosopher’s Walks for which k is 1, 2, and 3. The Philosopher’s Walk W2 consists of four W1 structures with the lower-left and the lower-right ones are 90 degree rotated clockwise and counter-clockwise, respectively; the upper ones have the same structure with W1. The same is true for any Wk for which the integer k is greater than 1. This rule has been devised by a mathematical philosopher David Hilbert (1862 – 1943), and the resulting pathway is usually called a HILBERT CURVE named after him. He once talked about a space filling method using this kind of curve to fill up a square with 2k sides, and every Philosophers’ Walk is designed according to this method.

Tae-Cheon is in charge of the rescue of the philosophers lost in Philosopher’s Walks using a hot air balloon. Fortunately, every lost philosopher can report Tae-Cheon the number of meter steps he has taken, and Tae-Cheon knows the length of a side of the square of the Philosopher’s Walk. He has to identify the location of the lost philosopher, the (x,y) coordinates assuming that the Philosopher’s Walk is placed in the 1st quadrant of a Cartesian plain with one meter unit length. Assume that the coordinate of the lower-left corner block is (1,1). The entrance of a Philosopher’s Walk is always at (1,1) and the exit is always (n,1) where n is the length of a side. Also assume that the philosopher have walked one meter step when he is in the entrance, and that he always go forward to the exit without back steps.

For example, if the number of meter-steps taken by a lost philosopher in the Philosopher’s Walk in W2 in Figure F.1(b) is 10, your program should report (3,4).

Your mission is to write a program to help Tae-Cheon by making a program reporting the location of the lost philosopher given the number of meter-steps he has taken and the length of a side of the square of the Philosopher’s Walk. Hurry! A philosopher urgently needs your help.

输入

Your program is to read from standard input. The input consists of a single line containing two positive integers, n and m, representing the length of a side of the square of the Philosopher’s Walk and the number of meter-steps taken by the lost philosopher, respectively, where n = 2k and m ≤ 22k for an integer k satisfying 0 < k ≤ 15.

输出

Your program is to write to standard output. The single output line should contain two integers, x and y, separated by a space, where (x,y) is the location of the lost philosopher in the given Philosopher’s Walk.

样例输入

4 10

样例输出

3 4

题意:就是给你图的大小,让你求出走一定步数所在的坐标。
为什么要换位置呢,其实就相当于把原本正向的图进行中心对称一样的翻转,从而让这个旋转
 #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int n,m; P solve(int n,int m)
{
if(n == )
{
if(m == )return P(,);
else if(m == )return P(,);
else if(m == )return P(,);
else return P(,);
}
int k = n/;
int part = m / (k*k);
P tmp = solve(n>>,m%(k*k));
if(part == )swap(tmp.first,tmp.second);
else if(part == )tmp.second+=k;
else if(part == )tmp.first+=k,tmp.second+=k;
else
{
P ret;
ret.first = k - tmp.second+;
ret.second = k - tmp.first+;
ret.first += k;
tmp = ret;
}
return tmp;
}
int main()
{
scanf("%d%d",&n,&m);
m--;
P ans = solve(n,m);
printf("%d %d\n",ans.first,ans.second);
}

最新文章

  1. 使linux服务器默认使用中文字符集zh_CN.UTF-8
  2. 开始使用Pyhton
  3. 如何在IIS 7.5中部署Asp.Net MVC 5的网站
  4. glusterfs rebalance
  5. hibernate实现增删改查的各种方法
  6. Unicode 编码解码
  7. Randomized QuickSelect
  8. 使用原始XML资源——使用原始XML文件
  9. Linux系统——运行级别
  10. pip相关工具使用小结
  11. composer的安装方法
  12. Java 中的纤程库 – Quasar
  13. 更换MariaDB数据库
  14. js中字符串和数组的使用
  15. 关于发邮件报错535 Error:authentication failed解决方法
  16. python-模块入门二(模块循环导入,区分python文件的两种用途,模块搜索路径,软件开发的目录规范)
  17. Gorm使用详解
  18. unity中实现场景之间加载进度条
  19. Redis 个人理解总结
  20. 关于markdown文件插入图片遇到的小问题和解决办法

热门文章

  1. (转)scikit-learn主要模块和基本使用方法
  2. oracle 根据一个时间段获取这个时间段内所有月份、天数、日期
  3. Vuejs的一些总结
  4. axis 数据流
  5. LeetCode(121):买卖股票的最佳时机
  6. 浅谈FastJson的TypeReference用法
  7. jenkins持续集成:定时构建语法
  8. Spring Boot如何使用Runner实现启动时调用?用法和原理都在这里
  9. PV-UV-QPS
  10. UPC 6616 Small Mulitple