NC15477. 喵呜
描述
输入描述
输入数据第一行包含一个正整数T，表示测试数据的组数，各组数据之间没有空行。
接下来T行，依次描述每组数据：
每组数据包含一行，包含六个正整数n、h、x、y、a、b，其含义见题目描述。
输出描述
输出由 T 组数据组成，各组数据之间没有空行。对于每一组数据：
若小猫可以成功离开樱花树，请输出她需要的最少跳跃次数。
若小猫无法通过给定的跳跃方法离开樱花树，请输出-1。
示例1
输入:
3 5 5 3 3 2 2 5 7 3 5 2 2 5 7 4 6 1 1
输出:
1 1 1
示例2
输入:
3 5 5 3 3 3 2 5 7 1 4 2 2 5 7 1 2 1 2
输出:
-1 -1 -1
示例3
输入:
4 999999999999 999999999999 454545454545 454545454545 1 1 777777777777 777777777777 343434343434 343434343434 1 1 777777777777 999999999999 343434343434 454545454545 1 1 999999999999 777777777777 454545454545 343434343434 1 1
输出:
454545454544 343434343433 -1 -1
C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 612K, 提交时间: 2019-02-03 16:11:11
#include <bits/stdc++.h>
using namespace std;
bool Dbg;
typedef double lf; typedef long long ll; typedef long double llf; typedef vector<int> vint; typedef unsigned int uint; typedef pair<int, int> pii; typedef unsigned long long ull;
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define mid ((l+r)>>1)
#define all(x) x.begin(), x.end()
#define debug(...) (Dbg ? void(fprintf(stderr, __VA_ARGS__)) : void())
#if __cplusplus <= 201103L
#define lop0(i,b) for (register int i = 0, i##end = (b); i < i##end; ++i)
#define lop1(i,b) for (register int i = 1, i##end = (b); i <= i##end; ++i)
#define dlop(i,a,b) for (register int i = (a), i##end = (b); i >= i##end; --i)
#define lop(i,a,b) for (register int i = (a), i##end = (b); i <= i##end; ++i)
#define dlop0(i,b) for (register int i = (b)-1; i >= 0; --i)
#define dlop1(i,b) for (register int i = (b); i >= 1; --i)
#else
#define lop0(i,b) for (int i = 0, i##end = (b); i < i##end; ++i)
#define lop1(i,b) for (int i = 1, i##end = (b); i <= i##end; ++i)
#define dlop(i,a,b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define lop(i,a,b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define dlop0(i,b) for (int i = (b)-1; i >= 0; --i)
#define dlop1(i,b) for (int i = (b); i >= 1; --i)
#endif
#if __cplusplus >= 201103L
mt19937 Rand(time(0) ^ (ull)(new char));
#define mt make_tuple
#else
uint Rand() {static uint x = time(0) ^ (ull)(new char); x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x;}
#endif
#define Debug(x) (Dbg ? void(cerr << #x << " = " << x << '\n') : void())
#define trav(it, a) for (__typeof((a).end())it = (a).begin(); it != (a).end(); ++it)
#define dtrav(it, a) for (__typeof((a).rend())it = (a).rbegin(); it != (a).rend(); ++it)
#define trav1(it, a) for (__typeof((a).end())it = (a).begin(), it##1; it != (a).end(); it = it1)
#define dtrav1(it, a) for (__typeof((a).rend())it = (a).rbegin(), it##1; it != (a).rend(); it = it1)
#define IS(x) (x == 10 || x == 13 || x == ' ')
#define OP operator
#define RT return *this
#define RX x=0;t=P();while((t<'0'||t>'9')&&t!='-')t=P();f=1;\
if(t=='-')t=P(),f=-1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RU x=0;t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x
#define WI if(x){if(x<0)P('-'),x=-x;c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WU if(x){c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
struct Cg {inline int operator()() {return getchar(); } }; struct Cp {inline void operator()(int x) {putchar(x); } };
struct Fr {
int f, t; Cg P;
#ifdef __SIZEOF_INT128__
inline Fr&OP, (__int128 &x) {RX; x *= f; RT; }
#endif
inline Fr&OP, (int &x) {RX; x *= f; RT; } inline Fr&OP, (ll &x) {RX; x *= f; RT; } inline Fr&OP, (char &x) {for (x = P(); IS(x); x = P()); RT; } inline Fr&OP, (string &x) {cin >> x; RT; } inline Fr&OP, (char *x) {char t = P(); for (; IS(t); t = P()); if (~t) {for (; !IS(t) && ~t; t = P()) * x++ = t; }*x++ = 0; RT; } inline Fr&OP, (lf &x) {scanf("%lf", &x); RT; } inline Fr&OP, (llf &x) {lf y; scanf("%lf", &y); x = y; RT; } inline Fr&OP, (uint &x) {RU; RT; } inline Fr&OP, (ull &x) {RU; RT; }
} in;
struct Fw {
int c, s[50]; Cp P;
#ifdef __SIZEOF_INT128__
inline Fw&OP, (__int128 x) {WI; RT; }
#endif
inline Fw&OP, (int x) {WI; RT; } inline Fw&OP, (uint x) {WU; RT; } inline Fw&OP, (ll x) {WI; RT; } inline Fw&OP, (ull x) {WU; RT; } inline Fw&OP, (char x) {P(x); RT; } inline Fw&OP, (lf x) {printf("%.5f", x); RT; } inline Fw&OP, (const llf &x) {printf("%.5f", lf(x)); RT; } inline Fw&OP, (const string &x) {cout << x; RT; } inline Fw&OP, (const char *x) {while (*x)P(*x++); RT; }
} out;
const int mod = 998244353, MAXN = 1e5 + 7, inft = 1e9 + 7; const ll infl = llf(1e18) + 1;
const lf eps = 1e-7;
template<typename T> inline T sqr(T x) {return x * x; }
template<typename A, typename B> inline A _gcd(A a, B b) {A t; if (a < b) swap(a, b); if (!b) return a; while (t = a % b) a = b, b = t; return b; }
template<typename A, typename B> inline ll _lcm(A a, B b) {return a / gcd(a, b) * 1ll * b; } template<typename T> inline T abs(T x) {return x >= 0 ? x : -x; }
template<typename A, typename B> inline ll mul(A a, B b, ll mod) {if (b < 0) b = -b, a = -a; ll ret; for (ret = 0; b; b >>= 1) {if (b & 1) ret = (ret + a) % mod; a = (a + a) % mod;} return ret % mod; }
template<typename A, typename B> inline A Pow1(A a, B b, int mod) {A ret; for (ret = 1; b; b >>= 1) {if (b & 1) ret = ret * 1ll * a % mod; a = a * 1ll * a % mod; } return ret % mod; }
template<typename A, typename B> inline ll Pow(A a, B b, ll mod) {assert(b >= 0); a %= mod; if (mod <= 2e9) return Pow1(a, b, mod); ll ret; for (ret = 1; b; b >>= 1) {if (b & 1) ret = mul(ret, a, mod); a = mul(a, a, mod); } return ret % mod; }
template<typename A, typename B> inline A max(A a, B b) {return a > b ? a : b; } template<typename A, typename B> inline A min(A a, B b) {return a < b ? a : b; } template<typename A, typename B> inline void chmax(A &x, B y) {if (x < y) x = y; } template<typename A, typename B> inline void chmin(A &x, B y) {if (x > y) x = y; } template<typename A, typename B> inline void amod(A &x, B y, int mod) {x += y; while (x < 0) x += mod; while (x > mod) x -= mod; } template<typename A> inline void Mod(A &x, int mod) {while (x < 0) x += mod; while (x > mod) x -= mod; }
inline void solve() {
ll ans = infl;
ll n, h, x, y, a, b;
in, n, h, x, y, a, b;
// n -= x, h -= y;
//x + ka = n x - ka = 1
//y + kb = h y - kb = 1
ll t1 = n - x, u1 = h - y, t2 = x - 1, u2 = y - 1;
if (t1 % a == 0) {
ll k1 = t1 / a;
if (u1 % b == 0 && (u1 / b % 2) == k1 % 2) chmin(ans, max(abs(k1), abs(u1 / b)));
if (u2 % b == 0 && (u2 / b % 2) == k1 % 2) chmin(ans, max(abs(k1), abs(u2 / b)));
}
if (t2 % a == 0) {
ll k2 = t2 / a;
if (u1 % b == 0 && (u1 / b) % 2 == k2 % 2) chmin(ans, max(abs(k2), abs(u1 / b)));
if (u2 % b == 0 && (u2 / b) % 2 == k2 % 2) chmin(ans, max(abs(k2), abs(u2 / b)));
}
out, ans == infl ? -1 : ans, '\n';
}
int main() {
#ifdef QvvQ
// freopen("data.in", "r", stdin), freopen("data.out", "w", stdout);
Dbg = 1;
#endif
int T;
in, T;
while (T--) solve();
#ifdef QvvQ
fprintf(stderr, "\ntime:%.5fms", clock() * 1.0 / CLOCKS_PER_SEC * 1000);
#endif
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 624K, 提交时间: 2020-03-25 21:02:03
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18;
ll T,n,h,x,y,a,b;
int main()
{
cin>>T;
while(T--)
{
ll ans=inf;
cin>>n>>h>>x>>y>>a>>b;
if((n-x)%a==0)
{
ll rw=(n-x)/a;
if((h-y)%b==0&&rw%2==((h-y)/b)%2)
{
ll cl=(h-y)/b;
ans=min(ans,max(rw,cl));
}
if((y-1)%b==0&&rw%2==((y-1)/b)%2)
{
ll cl=(y-1)/b;
ans=min(ans,max(rw,cl));
}
}
if((x-1)%a==0)
{
ll rw=(x-1)/a;
if((h-y)%b==0&&rw%2==((h-y)/b)%2)
{
ll cl=(h-y)/b;
ans=min(ans,max(rw,cl));
}
if((y-1)%b==0&&rw%2==((y-1)/b)%2)
{
ll cl=(y-1)/b;
ans=min(ans,max(rw,cl));
}
}
if(ans<inf)
cout<<ans<<endl;
else
cout<<-1<<endl;
}
}