UVa 10161

Ant on a Chessboard

from Volume 1. Elementary Problem Solving :: Maths - Misc

Problem

一只蚂蚁在棋盘上的 (1,1)，然后他按照如下蛇形走法：往上走一格，往右走一格，往下走一格，然后右走一格，往上走两格，再往左走两格……

蚂蚁的前 25 步如下：
25 24 23 22 21
10 11 12 13 20
09 08 07 14 19
02 03 06 15 18
01 04 05 16 17

输入一个整数 N，输出蚂蚁第 N 步所在的坐标。

Solution

设第 N 步所在的坐标为 (x,y)，令 z=max(x,y)，我们把符合 z=Z 的坐标都看作处于第 Z 层的坐标。从图中可以看出，同一层的数字是连续的并且方向是从下到上向左拐，或者从左到右向下拐。

可以发现，前 Z 层的数字不会大于 Z²。因此，我们可以根据 N 来确定 Z 的值，可以计算出 Z=ceil(sqrt(N))。

然后，我们可以计算出第 Z 层中最小值、最大值,然后计算出中值，up=sqr(Z) down=sqr(Z-1)+1 mid=(up+down)/2。计算出中值是因为：中值处于每一层的拐弯处，我们可以根据它来判断 N 处于这一层的前半段还是后半段。

由于每一层的方向不一样，所以最后我们还需要判断一下 Z 的奇偶性（Z 为奇数则该层的方向是从下往上向左拐，反之是从左往右向下拐），然后比较一下 N 和中值的大小，最后计算出坐标。