可能的路径[HackerRank] [英] Possible Paths [HackerRank]

问题描述

请参阅最近在HackerRank上发布的以下问题

Please see the following Question recently posted on HackerRank

亚当站在无限的2D网格中的点(a，b)上.他想知道他是否可以到达点(x，y).他唯一可以做的操作就是从某个点(a，b)移至(a + b，b)，(a，a + b)，(a-b，b)或(a，a-b)点.假定他可以移动到此2D网格上的任意点，即具有正(或负)X(或Y)坐标的点.告诉亚当他是否可以达到(x，y).

Adam is standing at point (a,b) in an infinite 2D grid. He wants to know if he can reach point (x,y) or not. The only operation he can do is to move to point (a+b,b), (a,a+b), (a-b,b), or (a,a-b) from some point (a,b). It is given that he can move to any point on this 2D grid,i.e., the points having positive or negative X(or Y) co-ordinates.Tell Adam whether he can reach (x,y) or not.

https://www.hackerrank.com/contests/infinitum- jun14/challenges/possible-path

我意识到x和y都必须是a和b的倍数之和...

I realized that both x and y must be a sum of some multiple of a and b...

因此x％(a + b)或x％(a-b)应该被a或b整除 对y ...

So x%(a+b) OR x%(a-b) should be divisible by either a or b and similarly for y...

但是以下方法不起作用...

But the following does not work ...

    long long int xb,yb,xa,ya;
    xb = x % b;
    xa = x % a;
    yb = y % b;
    ya = y % a;

    // for x
    bool cxbaplusb = a+b==0 ? xb == 0: (xb%(a+b))==0;
    bool cxbaminb = a-b==0 ? xb == 0: (xb%(a-b))==0;

    // for y
    bool cybaplusb = a+b==0 ? yb == 0: (yb%(a+b))==0;
    bool cybaminb = a-b==0 ? yb == 0: (yb%(a-b))==0;

    // for x
    bool cxaaplusb = a+b==0 ? xa == 0: (xa%(a+b))==0;
    bool cxaaminb = a-b==0 ? xa == 0: (xa%(a-b))==0;

    // for y
    bool cyaaplusb = a+b==0 ? ya == 0: (ya%(a+b))==0;
    bool cyaaminb = a-b==0 ? ya == 0: (ya%(a-b))==0;

    if ( (cxbaplusb || cxbaminb || cxaaplusb || cxaaminb)  && (cybaplusb || cybaminb || cyaaplusb || cyaaminb) )        
        std::cout << "YES" << std::endl;
    else
        std::cout << "NO" << std::endl;      

但是这不起作用...我错过任何条件了吗?有什么建议 ??

But this is not working ... Am I missing any conditions ? Any suggestions ??

推荐答案

以下数学解释可能会帮助您实现目标.

The following mathematical explanation may help you achieve your goal.

来源: https://hr -filepicker.s3.amazonaws.com/infinitum-jun14/editorials/2372-possible-path.pdf

这篇关于可能的路径[HackerRank]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！