G - Growing Rectangular Spiral

题意:
从原点出发,按照图中所示进行螺旋转弯,每一次转弯后的长度都必须比转弯前的长度长(至少长1),现给出第一象限的点坐标,问按此方式是否可以达到该点,若能则求出在总路径最短时的转弯次数及每段路径的长度(按递增顺序)。否则输出“NO PATH”。

题解:
三种情况
1.当x=y时,由于每段长度都至少比前一段长1个单位,因此不可能到达
2.当x<y时,只需要两次转弯即可,先走x,再走y即可
3.当x>y时,由于长度无上限,一圈即可到达,最多有6段。由于长度最少,刚开始三段必然1,2,3开始,特判y < 4.

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

#define lowbit(x) x & (-x)
#define lson left,mid,root << 1
#define rson mid+1,right,root << 1 | 1

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=1e5+100;


int main()
{
  int t;
  int p;
  int x, y;
  scanf("%d",&t);
  while(t --)
      {
        scanf("%d %d %d",&p,&x,&y);
        if(x == y || y < 4)
          {
          printf("%d ",p);
          puts("NO PATH");
          }
        else if(x < y)
          printf("%d 2 %d %d\n",p, x, y);
        else
          printf("%d 6 1 2 3 %d %d %d\n",p, x - y + 5, x + 2, x + 3);
      }
   return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注