ZOJ Problem Set–1414 Number Steps

Time Limit: 2 Seconds      Memory Limit: 65536 KB

---

Starting from point (0,0) on a plane, we have written all non-negative integers 0, 1, 2,... as shown in the figure. For example, 1, 2, and 3 has been written at points (1,1), (2,0), and (3, 1) respectively and this pattern has continued.

You are to write a program that reads the coordinates of a point (x, y), and writes the number (if any) that has been written at that point. (x, y) coordinates in the input are in the range 0...5000.

Input
The first line of the input is N, the number of test cases for this problem. In each of the N following lines, there is x, and y representing the coordinates (x, y) of a point.

Output
For each point in the input, write the number written at that point or write No Number if there is none.

Sample Input
3
4 2
6 6
3 4

Sample Output
6
12
No Number

乍一看这题目，我被这图吓到了，难道是什么高深的数学计算吗？仔细一看，原来只是用到了简单的数列知识而已。这个题目结合数列以及直线方程就可以很好的解决了。首先可以意识到这些数字的分布，是在两条直线上的，分别是：

y = x

y = x – 2

而每条直线上的数字又是有两个公差为4的等差数列构成，对于y = x，可以得到数列：

当x为偶数时：ax = 4*x/2;

当x为奇数时：ax = 4*(x+1)/2 - 3;

对于直线y  = x – 2,有：

当x为偶数时：ax = 4*x/2 – 2

当x为奇数时：ax = 4*(x – 1)/2 – 1

有了这些关系之后，程序呼之欲出啊，代码如下：

#include<iostream>
using namespace std;
int main()
{
  /*
  y = x
  an = 4n - 3 或 an = 4n
  y = x - 2
  an = 4n - 2 或 an = 4n - 1
  */
  int paires;cin>>paires;
  int x, y;
  while(paires-- && cin>>x>>y)
  {
    if(x == y)
    {
      if(x%2 == 0)
      {
        cout<<4*x/2<<endl;
      }
      else
      {
        cout<<4*(x+1)/2 - 3<<endl;
      }
    }
    else if( y == x - 2)
    {
      if(x%2 == 0)
      {
        cout<<4*x/2 - 2<<endl;
      }
      else
      {
        cout<<4*(x - 1)/2 - 1<<endl;
      }
    }
    else
      cout<<"No Number"<<endl;
  }
  return 0;
}