因为是从 (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>0||y>0){
- if(x%3==0&&y%3==0||x%3&&y%3)
- break;
- x=(x+1)/3;
- y=(y+1)/3;
- }
但是题目数据范围在 1e500 内
需要开高精度或者使用 Python 或 Java
下面展示 Java 程序作为参考
- /*
- Written By StelaYuri
- */
- 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");
- }
- }
来源: http://www.bubuko.com/infodetail-3395611.html