Hsueh- And Treasure

https://codeforces.cc/gym/322466/problem/H

 

题意

你在坐标轴原点（0，0），需要前往目标点（x，y），在i时刻最多可以向上下左右四个方向走i步，问：最少多长时间可以走到目标点。

题解

因为i时刻可以向四个方向走i步，到t时刻走的总步数即为：（t+1）*t/2，那么求最少时间即满足（t+1）*t/2 >=|x+y|，由于当仅仅满足上述不等式，在某些情况无法在所得t时刻走到目标点，根据样例观察可以发现，（t+1)*t/2>=|x+y|且两者同奇偶时，所得t可以完全到达目标点。那么可以考虑贪心的直接先x轴再y轴逼近目标点，最后到目标点附近进行上下横跳。

（大半夜补题，因为ll和输出格式wa了N发，气抖冷！┗|｀O′|┛）

AC代码

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<cctype>
  7 #include<iomanip>
  8 #include<map>
  9 #include<vector>
 10 #include<list>
 11 #include<deque>
 12 #include<stack>
 13 #include<queue>
 14 #include<set>
 15 #include<cctype>
 16 #include<string>
 17 #include<stdexcept>
 18 #include<fstream>
 19 #include<sstream>
 20 #include<sstream>
 21 #define mem(a,b) memset(a,b,sizeof(a))
 22 #define debug() puts("what the fuck!")
 23 #define dedebug() puts("what the fuck!!!")
 24 #define ll long long
 25 #define ull unsigned long long
 26 #define speed {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); };
 27 using namespace std;
 28 const double PI = acos(-1.0);
 29 const int maxn = 1e6 + 10;
 30 const int N = 1e3 + 10;
 31 const ll INF = 1e18;
 32 const ll mod = 1e9 + 7;
 33 const int inf = 0x3f3f3f3f;
 34 const double eps_0 = 1e-9;
 35 const double gold = (1 + sqrt(5)) / 2;
 36 template<typename T>
 37 inline void rd(T& x) {
 38     int f = 1; x = 0; char c = getchar();
 39     while (c<'0' || c>'9') { f = -1; c = getchar(); }
 40     while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
 41     x *= f;
 42 }
 43 template<typename T>
 44 inline T gcd(T a, T b) {
 45     return b ? gcd(b, a % b) : a;
 46 }
 47 ll t;
 48 ll judge(ll x, ll y) {
 49     ll fx = x & 1;
 50     ll fy = y & 1;
 51     if (fx == fy)return 1;
 52     return 0;
 53 }
 54 signed main() {
 55     rd(t);
 56     ll kase = 1;
 57     while (t--) {
 58         ll x, y;
 59         rd(x);
 60         rd(y);
 61         ll sum = abs(abs(x) + abs(y));
 62         ll pos = 0;
 63         printf("Case #%lld:\n", kase++);
 64         if (x == 0 && y == 0) {
 65             printf("0\n");
 66             continue;
 67         }
 68         for (ll i = 1; i <= maxn; ++i) {
 69             ll temp = (i + 1) * i / 2;
 70             if (judge(temp, sum) && sum <= temp) {
 71                 pos = i;
 72                 break;
 73             }
 74         }
 75         printf("%d\n", pos);
 76         ll cnt = 1;
 77         ll tx = abs(x), ty = abs(y);
 78         for (ll i = 1; i < pos; ++i) {
 79             if (cnt < tx) {
 80                 if (x > 0)printf("%lld 0\n", cnt);
 81                 else printf("%lld 0\n", -cnt);
 82             }
 83             else {
 84                 if (ty > abs(y)) {//如果在未到最后一步的情况下超出了目标点，需要开始横跳
 85                     if (y > 0)
 86                         printf("%lld %lld\n", x, ty - i);
 87                     else
 88                         printf("%lld %lld\n", x, -(ty - i));
 89                 }
 90                 else {
 91                     if (y > 0)printf("%lld %lld\n", x, cnt - tx);
 92                     else printf("%lld %lld\n", x, tx - cnt);
 93                 }
 94                 ty = cnt - tx;
 95             }
 96             cnt += i + 1;
 97         }
 98         printf("%lld %lld\n", x, y);
 99     }
100     return 0;
101 }