ZJNU 1534 - Problem Robot--高级

因为是从(0,0)点开始以1,3,9,27,....的步数走的

其实可以每走一步后，以机器人为中心，平面所有坐标全部缩小3倍

那么本应该走3步的路现在只需要走1步就可以到达那个点

那么对于机器人来说这种变化意味着什么

走一步，缩小3倍，再走一步，再缩小3倍

以原点(0,0)为参照物，机器人走的距离确实是以1,3,9,27,...递增的

但是以机器人为参照物的话，每次它都只走了1步

然后，考虑在某个时刻，机器人和它的目标坐标(x,y)的相对坐标距离为(Δx,Δy)

因为接下来机器人要走的步数是1,3,9,...

因为有1的出现，所以Δx和Δy不可能同时是3的倍数，也不可能都不是3的倍数

如果出现了这种情况，直接输出Impossible

其余的，因为每次都会让接下来要走的步数/3

可能会出现类似-1-3+9的情况

这种情况下如果按照思路应该是-1/3-3/3+9/3=-1+3=2

但是如果直接进行整除

(-1-3+9)/3=5/3=1

不符合思路

所以需要将%3时先后为2,0,1的数归在一起

C语言的程序主要功能描述如下

x=abs(x);

y=abs(y);

while(x>||y>){

    if(x%==&&y%==||x%&&y%)

        break;

    x=(x+)/;

    y=(y+)/;

}

但是题目数据范围在1e500内

需要开高精度或者使用Python或Java

下面展示Java程序作为参考

import java.util.Scanner;

import java.math.BigInteger;

public class Main

{

    public static void main(String[] args)

    {

        Scanner in=new Scanner(System.in);

        BigInteger a=new BigInteger(in.next()).abs(),b=new BigInteger(in.next()).abs(),j1,j2;

        BigInteger c0=BigInteger.ZERO,c1=BigInteger.ONE,c2=new BigInteger("2"),c3=new BigInteger("3");

        boolean jd=true;

        while(jd&&(a.compareTo(c0)!=0||b.compareTo(c0)!=0)){

            j1=a.remainder(c3);

            j2=b.remainder(c3);

            if((j1.compareTo(c0)==0)==(j2.compareTo(c0)==0)){

                jd=false;

                break;

            }

            a=a.add(c1).divide(c3);

            b=b.add(c1).divide(c3);

        }

        if(jd)

            System.out.println("Possible\n");

        else

            System.out.println("Impossible\n");

    }

}

巴特西

ZJNU 1534 - Problem Robot--高级

最新文章

热门文章