第九届蓝桥杯省赛JAVA真题----螺旋折线
题目
标题:螺旋折线
如图p1.pgn所示的螺旋折线经过平面上所有整点恰好一次。
对于整点(X, Y),
我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。
例如dis(0, 1)=3, dis(-2, -1)=9
给出整点坐标(X, Y),你能计算出dis(X, Y)吗?
【输入格式】
X和Y
对于40%的数据,-1000 <= X, Y <= 1000
对于70%的数据,-100000 <= X, Y <= 100000
对于100%的数据, -1000000000 <= X, Y <= 1000000000
【输出格式】
输出dis(X, Y)
【输入样例】
0 1
【输出样例】
3
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是:Main,否则按无效代码处理。
分析
首先(0,0)到原点的距离为0 ,(-1,0)到原点的距离为1
(-1,1)=(-1,0)+1
(0,1) = (-1,1)+1
这里规律就已经很明显了,用递归
(x,y)到原点的距离就是(x,y)前一个点到原点的距离+1
这里的问题就是求(x,y)前一个点
观察给的图可以看出这里需要对四个象限进行判断。
其中第一象限,第二象限,第四象限在 |x|==|y|时会转变方向,第三象限中,假设给定的点横坐标是x(x<0),那么将会在(x,x+1)处换边方向
代码
package Winter;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
/*public static void main(String[] args) {
BigInteger a = new BigInteger("5");
BigInteger b = new BigInteger("4");
System.out.println(a.compareTo(b)); //小于则返回-1,等于则返回0,大于则返回1
}*/
static BigInteger data1 = new BigInteger("0");
static BigInteger data2 = new BigInteger("-1");
static BigInteger data3 = new BigInteger("1");
public static BigInteger dp(BigInteger x,BigInteger y) {
if(x.compareTo(data1)==0&&y.compareTo(data1)==0) return data1;
if(x.compareTo(data2)==0&&y.compareTo(data1)==0) return data3;
if(x.compareTo(data1)==0 || y.compareTo(data1)==0) {
if(y.compareTo(data1)==0) {
if(x.compareTo(data1)==-1) return dp(x,y.subtract(data3)).add(data3);
if(x.compareTo(data1)==1) return dp(x,y.add(data3)).add(data3);
}
if(x.compareTo(data1)==0) {
if(y.compareTo(data1)==1) return dp(x.subtract(data3),y).add(data3);
if(y.compareTo(data1)==-1) return dp(x.add(data3),y).add(data3);
}
}else {
if(x.compareTo(data1)==-1&&y.compareTo(data1)==1) {
if(x.abs().compareTo(y)==-1) return dp(x.subtract(data3),y).add(data3);
else return dp(x,y.subtract(data3)).add(data3);
}
if(x.compareTo(data1)==1&&y.compareTo(data1)==1) {
if(y.compareTo(x)==-1) return dp(x,y.add(data3)).add(data3);
else return dp(x.subtract(data3),y).add(data3);
}
if(x.compareTo(data1)==1&&y.compareTo(data1)==-1) {
if(y.abs().compareTo(x)==1) return dp(x.add(data3),y).add(data3);
else return dp(x,y.add(data3)).add(data3);
}
if(x.compareTo(data1)==-1&&y.compareTo(data1)==-1) {
if(x.abs().compareTo(y.abs().add(data3))==1) return dp(x,y.subtract(data3)).add(data3);
else return dp(x.add(data3),y).add(data3);
}
}
return data1;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
BigInteger x = s.nextBigInteger();
BigInteger y = s.nextBigInteger();
BigInteger num;
num =dp(x,y);
System.out.println(num);
}
}
结果
输入
0 1
输出
3