~~~
# Delta-wave
Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6931????Accepted Submission(s): 2674
~~~
Problem Description
A triangle field is numbered with successive integers in the way shown on the picture below.?

The traveller needs to go from the cell with number M to the cell with number N. The traveller is able to enter the cell through cell edges only, he can not travel from cell to cell through vertices. The number of edges the traveller passes makes the length of the traveller's route.?
Write the program to determine the length of the shortest route connecting cells with numbers N and M.?
Input
Input contains two integer numbers M and N in the range from 1 to 1000000000 separated with space(s).
Output
Output should contain the length of the shortest route.
Sample Input
~~~
6 12
~~~
?
Sample Output
~~~
3
~~~
**求最近的路徑的大小,本質上這個題中每一個塊可以表示為三個坐標的形式,那就是水平方向的第幾層,左側的左側第幾列,右側看右側第幾列,比如說:1這個元素在水平第1層,左側第1列,右側第1列; 6這個元素是水平第3層,左側第2層,右側第1層,那么1到6的計算就是這三個坐標的差的絕對值之和:2+1+0 = 3 ,也就是說1到6需要3步。**
剩下的自然是怎么求出來各個方向上的位置咯:水平方向是level = sqrt(num - 1) + 1,左側的坐標可以表示為:left = ( level*level - num)/ 2 +1,?
右側的坐標可以表示為:right = (num- (level-1)*(level-1) - 1)/ 2 + 1
那么剩下的就是將兩個點的三個坐標的值對應求差然后去絕對值再求和就可以了
~~~
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext())
{
int num1 = scanner.nextInt();
int num2 = scanner.nextInt();
int level1 = (int)Math.sqrt(num1 - 1) + 1;
int left4num1 = (level1*level1 - num1)/2 + 1;
int right4num1 = (num1 - (level1 - 1) * (level1 - 1) - 1)/2 + 1;
int level2 = (int)Math.sqrt(num2 - 1) + 1;
int left4num2 = (level2*level2 - num2)/2 + 1;
int right4num2 = (num2 - (level2 - 1) * (level2 - 1) - 1)/2 + 1;
System.out.println(Math.abs(level1 - level2) + Math.abs(left4num1 - left4num2) + Math.abs(right4num1 - right4num2));
}
}
}
~~~
- 前言
- 求和的問題ACM
- A+B問題acm
- 1091ACM求和
- 杭電ACM1092求和問題詳解
- ACM杭電的1093求和問題
- 杭電ACM1094計算A+B的問題
- 杭電ACM1095解決A+B問題
- 杭電ACM1096求和問題
- 杭電Acm1001解決求和的問題
- 杭電ACM1008電梯問題C++
- 杭電ACM大賽2000關于ASCII碼排序的問題
- 杭電ACM2006奇數的乘積
- 杭電ACM數值統計2008
- 杭電ACM1019求最大公約數
- 杭電ACM1108求最小公倍數
- 杭電ACM2035人見人愛的A^B
- 杭電ACM1061N^N求最右邊的數的問題
- 杭電ACM1021裴波納挈數AGAIN
- 杭電ACm1005求f(n)非遞歸
- 杭電ACM1071The area---------求積分面積
- 杭電ACM吃糖果問題
- 杭電ACm求數列的和2009
- 杭電ACM多項式求和--》2011
- 杭電ACM。。。sort
- 杭電ACM1004
- 杭電ACM2043密碼的問題已經AC
- 杭電ACM2041樓梯問題
- 動態規劃C++::杭電ACM1003
- 杭電ACM----2018母牛的故事
- 杭電ACM2007平方和與立方和
- 盧卡斯隊列
- 全國軟件2. 三人年齡
- 全國軟件3. 考察團組成
- 全國軟件--微生物增殖
- 全國軟件填寫算式
- 全國軟件-----------猜生日
- 全國軟件---------歐拉與雞蛋
- Java經典算法四十例編程詳解+程序實例
- 杭電ACMA + B Problem II問題解析
- 杭電ACM1018BigNumber解析
- 杭電ACM1088 Write a simple HTML Browser Java
- 杭電ACM1106排序Java代碼
- 杭電ACM 1012 u Calculate e java
- 杭電ACM 1020 Encoding java解析
- 杭電1047 An Easy Task - java 解讀
- 杭電ACM 1040 As Easy As A+B java 解讀
- 杭電ACM 1041 Computer Transformation java代碼詳解AC
- 杭電ACM 1030 Delta-wave java代碼解析