【规律】Growing Rectangular Spiral

Growing Rectangular Spiral

题目描述

A growing rectangular spiral is a connected sequence of straightline segments starting at the origin. The fi rst segment goes right (positive x direction). The next segment goes up (positive y direction). The next segment goes left (negative x direction). The next segment goes down (negative y direction) and the sequence of directions repeats. Each segment has integer length and each segment is at least one unit longer than the previous segment. In the spiral on the right, the segment lengths are 1, 2, 4, 6, 7, 9,11, 12, 15, 20.
Write a program to determine the shortest growing rectangular spiral (in total length) that ends at a given integer point (x, y) in the fi rst quadrant or determine that there is no such spiral.

输入

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.
Each data set consists of a single line of input consisting of three space separated decimal integers.
The first integer is the data set number. The next two integers are the x and y coordinates of the desired end point (1 ≤ x ≤ 10000, 1 ≤ y ≤ 10000).

输出

For each data set there is a single line of output. If there is no spiral solution, the line consists of the data set number, a single space and ‘NO PATH’ (without the quotes). If there is a solution, the line consists of the data set number, a single space, the number of segments in the solution, a single space,followed by the lengths of the segments in order, separated by single spaces. The input data will be chosen so that no path requires more than 22 segments.

样例输入

样例输出

1 NO PATH

2 2 3 5

3 6 1 2 3 9 10 11

【题解】

　　问是否存在一条螺旋折线使得跑到（x，y）点，每一次转折都是严格递增的顺序。

　　请输出存在的路径。如果没有则输出"NO PATH"

【规律】

　　1、如果是（x，y）y>x明显是有一条两次转折到达的点。

　　2、如果　　y==x，是不存在这样的路径。

　　3、如果是 x<y，其实是利用x，y的差值关系来构建出来6步达到的效果，具体看代码。

 #pragma GCC optimize("Ofast,no-stack-protector")

 #pragma GCC optimize("O3")

 #pragma GCC optimize(2)

 #include <bits/stdc++.h>

 #define inf 0x3f3f3f3f

 #define linf 0x3f3f3f3f3f3f3f3fll

 #define pi acos(-1.0)

 #define nl "\n"

 #define pii pair<ll,ll>

 #define ms(a,b) memset(a,b,sizeof(a))

 #define FAST_IO ios::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL)

 using namespace std;

 typedef long long ll;

 const int mod = ;

 ll qpow(ll x, ll y){ll s=;while(y){if(y&)s=s*x%mod;x=x*x%mod;y>>=;}return s;}

 //ll qpow(ll a, ll b){ll s=1;while(b>0){if(b%2==1)s=s*a;a=a*a;b=b>>1;}return s;}

 inline int read(){int x=,f=;char ch=getchar();while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();return x*f;}

 const int N = 1e5+;

 int main()

 {

     int _, cas, x, y;

     for(scanf("%d",&_);_--;)

     {

         scanf("%d",&cas);

         scanf("%d%d",&x,&y);

         printf("%d ",cas);

         if(x==y) puts("NO PATH");

         else if(x<y){

             printf("2 %d %d\n",x,y);

         }

         else{

             if(y<) puts("NO PATH");

             else{

                 printf("6 1 2 3 %d %d %d\n",x+-y+, x+, x+);

             }

         }

     }

 }

巴特西